An MDL approach to efficiently discover communities in bipartite network

Abstract

An minimum description length (MDL) criterion is proposed to choose a good partition for a bipartite network. A heuristic algorithm based on combination theory is presented to approach the optimal partition. As the heuristic algorithm automatically searches for the number of partitions, no user intervention is required. Finally, experiments are conducted on various datasets, and the results show that our method generates higher quality results than the state-of-art methods, cross-association and bipartite, recursively induced modules. Experiment results also show the good scalability of the proposed algorithm. The method is applied to traditional Chinese medicine (TCM) formula and Chinese herbal network whose community structure is not well known, and found that it detects significant and it is informative community division.

Keywords

community detection / bipartite network / minimum description length

References

[1] AngiulliF, CesarioE, PizzutiC. Random walk biclustering for microarray data [J]. Information Sciences, 2008, 178(6): 1479-1497

[2] AntiqueiraL, Oliveira JrO N, CostaL F, NunesM G V. A complex network approach to text summarization [J]. Information Sciences, 2009, 179(5): 584-599

[3] CaiK Y, YinB B. Software execution processes as an evolving complex network [J]. Information Sciences, 2009, 179(12): 1903-1928

[4] HruschkaE, CampelloR, CastroL D. Evolving clusters in gene-expression data [J]. Information Sciences, 2006, 176(13): 1898-1927

[5] JenkinsS, KirkS R. Software architecture graphs as complex networks: A novel partitioning scheme to measure stability and evolution [J]. Information Sciences, 2007, 177(12): 2587-2601

[6] DANON L, DIAZ-GUILERA A, DUCH J, ARENAS A. Comparing community structure identification [EB/OL]. [2012-9-20] http://iopscience.iop.org/1742-5468/2005/09/P09008.

[7] GuimeràR, AmaralL. Functional cartography of complex metabolic networks [J]. Nature, 2005, 433: 895-900

[8] LindenG, SmithB, YorkJ. Amazon.com recommendations: Item-to-Item collaborative filtering [J]. IEEE Internet Computing, 2003, 7(1): 76-80

[9] NewmanM E J. The structure and function of complex networks [J]. SIAM Review, 2003, 45(2): 167-256

[10] NewmanM E J, GirvanM. Finding and evaluating community structure in networks [J]. Physical Review E, 2003, 69(2): 026113

[11] NewmanM E J. Modularity and community structure in networks [J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582

[12] PujolJ, BéjarJ, DelgadoJ. Clustering algorithm for determining community structure in large networks [J]. Physical Review E, 2006, 74(1): 016107

[13] FortunatoS, BarthelemyM. Resolution limit in community detection [J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41

[14] RosvallM, BergstromC T. An information-theoretic framework for resolving community structure in complex networks [J]. Proceedings of the National Academy of Sciences, 2007, 104(18): 7327-7331

[15] RosvallM, BergstromC T. Maps of random walks on complex networks reveal community structure [J]. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118-1123

[16] BarronA, RissanenJ, YuB. The minimum description principle in coding and modeling [J]. IEEE Transactions on Information Theory, 1998, 44(6): 2743-2760

[17] StrogatzS H. Exploring complex networks [J]. Nature, 2001, 410: 268-276

[18] ChakrabartiD, PapadimitriouS, ModhaD S, FaloutsosC. Fully automatic cross-associations [C]. Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004, New York, ACM: 79-88

[19] BarberM J. Modularity and community detection in bipartite network [J]. Physical Review E, 2007, 76(6): 066102

[20] MadeiraS C, OliveiraA L. Biclustering algorithms for biological data analysis: A survey [J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004, 1(1): 24-45

[21] ChengY, ChurchG M. Biclustering of expression data [C]. Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, 2000, California, AAAI: 93-103

[22] DhillonI S, MallelaS, ModhaD S. Information-theoretic co-clustering [C]. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, New York, ACM: 89-98

[23] GuimeràR, Sales-PardoM, AmeralL. Module identification in bipartite and directed networks [J]. Physical Review E, 2007, 76(3): 036102

[24] LehmannS, SchwartzM, HansenL K. Biclique communities [J]. Physical Review E, 2008, 78(1): 016108

[25] SunJ, FaloutsosC, PapadimitriouS, YuP. GraphScope: Parameter-free mining of large time-evolving graphs [C]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007, New York, ACM: 687-696

[26] PapadimitriouS, SunJ, FaloutsosC, YuP. Hierarchical, parameter-free community discovery [C]. Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, 2008, Berlin, Springer-Verlag: 170-187

[27] RosenK HDiscrete mathematics and its applications [M], 19994th editionBoston, WCB/McGraw-Hill

[28] GirvanM, NewmanM E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826

[29] SipserMIntroduction to the theory of computation [M], 1997, Boston, PWS Publishing Company

[30] AshlockDEvolutionary computation for modeling and optimization [M], 2005, New York, Springer

[31] XuK K, LiuY T, TangR, ZuoJ, ZhuJ, TangC J. A novel method for real parameter optimization based on gene expression programming [J]. Applies Soft Computing, 2009, 9(2): 725-737

[32] DavisA, GardnerB B, GardnerM RDeep south [M], 1941, Chicago, University of Chicago Press

[33] FreemanLDynamic social network modeling and analysis [M], 2003, Washington, The National Academies Press