A Structural Based Community Similarity Algorithm and Its Application in Scientific Event Detection

Abstract

Graph similarity has been a crucial topic in network science, and is widely used in network dynamics, graph monitoring and anomalous event detection. However, few studies have paid attention to community similarity. The fact that communities do not necessarily own sub-modularity structure determines that graph similarity algorithms can not be applied to communities directly. Besides, the existing graph similarity algorithms ignore the organization structure of networks. Two communities can be regarded as the same when both their vertices and structure are identical. Thus the existing algorithms are unable to detect anomalous events about the shift of communities’ organization structure. In this paper, we propose a novel community similarity algorithm, which considers both the shift of vertices and the shift of communities’ layered structure. The layered structure of communities categorizes nodes into different groups, depending on their influence in the community. Both the influence of each node and the shift of nodes’ influence are expected to affect the similarity of two communities. Experiments on the synthetic data show that the novel algorithm performs better than the state-of-art algorithms. Besides, we apply the novel algorithm on the scientific data set, and identify meaningful anomalous events occurred in scientific mapping. The anomalous events are proved to correspond to the transition of topics for journal communities. It demonstrates that the novel algorithm is effective in detecting the anomalous events about the transition of communities’ structure.

Publication
Intelligence and Security Informatics: 12th Pacific Asia Workshop, PAISI 2017, Jeju Island, South Korea, May 23, 2017, Proceedings 12