Avatar Path Clustering in Networked Virtual Environments

With the increase of network bandwidth and the advance of 3D graphics technology, networked virtual environments (NVEs) have become popular recently. Early SIMNET and currently booming massively multiplayer online games (MMOGs), such as Second Life (SE) and World of War craft (WoW), are examples of NVEs. Because NVE users, interests or habits may be similar, avatars, or the representative of NVE users, may have similar behavior patterns, which leads to similar motion paths in the NVE. This paper proposes two NVE avatar path clustering algorithms, namely, Average Distance of Corresponding Points-Density Clustering (ADCP-DC) and Longest Common Subsequence-Density Clustering (LCSS-DC). Given avatar paths, both algorithms will produce a collection of path clusters and their representative paths (RPs), which can be used to analyze avatar behaviors for improving NVE design. We take SE user trace data as input of the algorithms to demonstrate their applicability. We also show how to adjust algorithm parameters to obtain high-quality path clustering in terms of silhouette coefficient and cluster coverage.