Community Detection in Large-Scale Bipartite Networks

ABSTRACT

Community detection in networks receives much attention recently. Most of the previous works are for unipartite networks composed of only one type of nodes. In real world situations, however, there are many bipartite networks composed of two types of nodes. In this paper, we propose a fast algorithm called LP&BRIM for community detection in large-scale bipartite networks. It is based on a joint strategy of two developed algorithms -- label propagation (LP), a very fast community detection algorithm, and BRIM, an algorithm for generating better community structure by recursively inducing divisions between the two types of nodes in bipartite networks. Through experiments, we demonstrate that this new algorithm successfully finds meaningful community structures in large-scale bipartite networks in reasonable time limit.

References

1. M. Girvan and M. E. J. Newman, "Community structure in social and biological networks," Proceedings of the National Academy of Sciences of the United States of America, vol. 99, Jun., 2002, pp. 7821-7826.
2. I. X. Y. Leung, P. Hui, P. Lio, and J. Crowcroft, "Towards real time community detection in large networks," Phys. Rev. E, vol. 79, no. 6, 066107, 2009.
3. M. E. J. Newman, "Finding community structure in networks using the eigenvectors of matrices," Phys. Rev. E, vol. 74, 036104, Sep. 2006.
4. L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, "Comparing community structure identification," J. Stat. Mech., P09008, Sep. 2005, doi: 10.1088/1742-5468/2005/09/P09008.
5. M. J. Barber, "Modularity and community detection in bipartite network," Phys. Rev. E, vol. 76, no. 6, 066102, Dec. 2007, doi: 10.1103/PhysRevE.76.066102.
6. U. N. Raghavan, R. Albert, and S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Phys. Rev. E, vol. 76, no. 3, 036106, Sep. 2007, doi: 10.1103/PhysRevE.76.036106.
7. R. Guimera, M. Sales-Pardo, and L. A. N. Amaral, "Module identification in bipartite and directed networks," Phys. Rev. E, vol. 76, no. 3, 036102, Sep. 2007, doi: 10.1103/PhysRevE.76.036102.
8. M. E. J. Newman, "Modularity and community structure in networks," Proceedings of the National Academy of Sciences of the United States of America, vol. 103, no. 23, Jun., 2006, pp. 8577-8582, doi: 10.1073/pnas.0601602103.
9. A. Davis, B. B. Gardner, and M. R. Gardner, Deep South, University of Chicago Press, 1941.
10. S. Fortunato, and C. Castellano, "Community structure in graphs," Dec. 2007, arXiv:0712.2716.
11. J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, "Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters," 2008, arXiv:0810.1355.
12. S. Fortunato, and M. Barthelemy, "Resolution limit in community detection," Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no. 1, Jan. 2007, pp. 36-41, doi: doi:10.1073/pnas.0605965104.
13. S. Lehmann, M. Schwartz, and L. K Hansen, "Biclique communities," Phys. Rev. E, vol. 78, no. 1, 016108, 2008, doi: 10.1103/PhysRevE.78.016108.
14. T. Murata, "Detecting communities from bipartite networks based on bipartite modularities", Proceedings of the 2009 IEEE International Conferene on Social Computing (SocialCom 09), Aug. 2009, in press.
15. K. Wakita, and K. Suzuki, "Extracting multi-facet community structure from bipartite networks," Proceedings of the International Symposium on Social Intelligence and Networking (SIN 09), Aug. 2009, in press.
16. X. Liu, T. Murata, "How does label propagation algorithm work in bipartite networks?" Proceedings of the 2009 International Workshop on Intelligent Web Interaction (IWI 09), Sep. 2009, in press.

Index Terms

• Human-centered computing

  • Collaborative and social computing

• Information systems

  • Information retrieval

    • Evaluation of retrieval results

    • Retrieval tasks and goals

      • Clustering and classification

  • Information storage systems

    • Storage architectures

      • Storage network architectures

  • Information systems applications

    • Data mining

      • Clustering

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows