关键词: 复杂网络, 社区结构, 数据挖掘

Abstract: The ability to efficiently and effectively mine community structures from real-world complex networks is fundamental for both theoretical research and practical applications. Although there are many works with regard to community mining, few of them study the connections between the local distance among nodes and the global community structures of networks. This paper studies the issue and finds that the nodes with nearer (or further) dis-tance tend to belong to the same (or distinct) community with bigger probabilities, meanwhile the distance among nodes within the same (or distinct) communities tend to be smaller (or larger). Based on the heuristic in terms of the link between distance and community structure, the paper proposes a distance-based similarity measure as well as a novel community mining algorithm DSA, and validates the DSA through rigorously testing it against several benchmark networks. The experimental results show that the DSA is able to accurately discover the potential com-munities with their hierarchical structures from the tested benchmark networks.

Key words: complex network, community structure, data mining