A novel clustering algorithm based upon games on evolving network

作者：Li, Qiang^*; Chen, Zhuo; He, Yan; Jiang, Jing-ping

来源：Expert Systems with Applications, 2010, 37(8): 5621-5629.

DOI：10.1016/j.eswa.2010.02.050

• Unsupervised learning
• Data clustering
• Evolutionary game theory
• Evolutionarily stable strategy

This paper introduces a model based upon games on an evolving network, and develops three clustering algorithms according to it. In the clustering algorithms, data points for clustering are regarded as players who can make decisions in games. On the network describing relationships among data points, an edge-removing-and-rewiring (ERR) function is employed to explore in a neighborhood of a data point, which removes edges connecting to neighbors with small payoffs, and creates new edges to neighbors with larger payoffs. As such, the connections among data points vary over time. During the evolution of network, some strategies are spread in the network. As a consequence, clusters are formed automatically, in which data points with the same evolutionarily stable strategy are collected as a cluster, so the number of evolutionarily stable strategies indicates the number of clusters. Moreover, the experimental results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the comparison with other algorithms also provides an indication of the effectiveness of the proposed algorithms.

• 出版日期2010-8
• 单位浙江大学; 上海交通大学