一种改进的社区检测算法

Graph partitioning is traditionally designed for dividing the vertices into clusters such that a predefined quality function, for example, normalized cut or ratio cut, is approximately optimized. Recently, demand for social network analysis arouses the new research interest on graph clustering with no constraint on the size of partitions. Social network exhibits some key properties such as power-law and small-world. This paper presents a new definition for measuring the small world weight between two vertices, then a refinement strategy is designed for improving results obtained by traditional graph partitioning algorithm. Experimental evaluation demonstrates that the proposed algorithm can effectively enhance the objective functions.