Link community detection using generative model and nonnegative matrix factorization.
Discovery of communities in complex networks is a fundamental data analysis problem with applications in various domains. While most of the existing approaches have focused on discovering communities of nodes, recent studies have shown the advantages and uses of link community discovery in networks. Generative models provide a promising class of techniques for the identification of modular structures in networks, but most generative models mainly focus on the detection of node communities rather than link communities. In this work, we propose a generative model, which is based on the importance of each node when forming links in each community, to describe the structure of link communities. We proceed to fit the model parameters by taking it as an optimization problem, and solve it using nonnegative matrix factorization. Thereafter, in order to automatically determine the number of communities, we extend the above method by introducing a strategy of iterative bipartition. This extended method not only finds the number of communities all by itself, but also obtains high efficiency, and thus it is more suitable to deal with large and unexplored real networks. We test this approach on both synthetic benchmarks and real-world networks including an application on a large biological network, and compare it with two highly related methods. Results demonstrate the superior performance of our approach over competing methods for the detection of link communities.
College of Computer Science and Technology, Jilin University, Changchun, China ; Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, China.
Dongxiao
D
He
Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, China ; School of Computer Science and Technology, Tianjin University, Tianjin, China ; School of Design, Engineering, and Computing, Bournemouth University, Poole, Dorset, United Kingdom.
Di
D
Jin
HASLab, INESC TEC and University of Minho, Braga, Portugal.
Carlos
C
Baquero
College of Computer Science and Technology, Jilin University, Changchun, China ; Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, China.
Dayou
D
Liu
D000465:Algorithms; D000818:Animals; D019058:Community Networks; D006801:Humans; D008962:Models, Theoretical; D060066:Protein Interaction Maps; D012111:Residence Characteristics; D012441:Saccharomyces cerevisiae / Q000378:metabolism; D029701:Saccharomyces cerevisiae Proteins / Q000378:metabolism
D029701:Saccharomyces cerevisiae Proteins