An MDL approach to efficiently discover communities in bipartite network

详细信息    查看全文

• 作者：Kai-kuo Xu (1)
  Chun-qiu Zeng (2)
  Chang-an Yuan (3)
  Chuan Li (4)
  Chang-jie Tang (4)
  
• 关键词：community detection ; bipartite network ; minimum description length
• 刊名：Journal of Central South University
• 出版年：2014
• 出版时间：April 2014
• 年：2014
• 卷：21
• 期：4
• 页码：1353-1367
• 全文大小：
• 参考文献：1. ANGIULLI F, CESARIO E, PIZZUTI C. Random walk biclustering for microarray data [J]. Information Sciences, 2008, 178(6): 1479-497. CrossRef
  2. ANTIQUEIRA L, OLIVEIRA JR O N, COSTA L F, NUNES M G V. A complex network approach to text summarization [J]. Information Sciences, 2009, 179(5): 584-99. CrossRef
  3. CAI K Y, YIN B B. Software execution processes as an evolving complex network [J]. Information Sciences, 2009, 179(12): 1903-928. CrossRef
  4. HRUSCHKA E, CAMPELLO R, CASTRO L D. Evolving clusters in gene-expression data [J]. Information Sciences, 2006, 176(13): 1898-927. CrossRef
  5. JENKINS S, KIRK S R. Software architecture graphs as complex networks: A novel partitioning scheme to measure stability and evolution [J]. Information Sciences, 2007, 177(12): 2587-601. CrossRef
  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, AMARAL L. Functional cartography of complex metabolic networks [J]. Nature, 2005, 433: 895-00. CrossRef
  8. LINDEN G, SMITH B, YORK J. Amazon.com recommendations: Item-to-Item collaborative filtering [J]. IEEE Internet Computing, 2003, 7(1):76-0. CrossRef
  9. NEWMAN M E J. The structure and function of complex networks [J]. SIAM Review, 2003, 45(2): 167-56. CrossRef
  10. NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks [J]. Physical Review E, 2003, 69(2): 026113. CrossRef
  11. NEWMAN M E J. Modularity and community structure in networks [J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-582. CrossRef
  12. PUJOL J, BéJAR J, DELGADO J. Clustering algorithm for determining community structure in large networks [J]. Physical Review E, 2006, 74(1): 016107. CrossRef
  13. FORTUNATO S, BARTHELEMY M. Resolution limit in community detection [J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-1. CrossRef
  14. ROSVALL M, BERGSTROM C T. An information-theoretic framework for resolving community structure in complex networks [J]. Proceedings of the National Academy of Sciences, 2007, 104(18): 7327-331. CrossRef
  15. ROSVALL, M, BERGSTROM C T. Maps of random walks on complex networks reveal community structure [J]. Proceedings of the National Academy of Sciences, 2008, 105(4):1118-123. CrossRef
  16. BARRON A, RISSANEN J, YU B. The minimum description principle in coding and modeling [J]. IEEE Transactions on Information Theory, 1998, 44(6): 2743-760. CrossRef
  17. STROGATZ S H. Exploring complex networks [J]. Nature, 2001, 410: 268-76. CrossRef
  18. CHAKRABARTI D, PAPADIMITRIOU S, MODHA D S, FALOUTSOS C. Fully automatic cross-associations [C]// Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2004: 79-8.
  19. BARBER M J. Modularity and community detection in bipartite network [J]. Physical Review E, 2007, 76(6): 066102. CrossRef
  20. MADEIRA S C, OLIVEIRA A L. Biclustering algorithms for biological data analysis: A survey [J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004, 1(1): 24-5.
  21. CHENG Y, CHURCH G M. Biclustering of expression data [C]// Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology. California: AAAI, 2000: 93-03.
  22. DHILLON I S, MALLELA S, MODHA D S. Information-theoretic co-clustering [C]// Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003: 89-8. CrossRef
  23. GUIMERà R, SALES-PARDO M, AMERAL L. Module identification in bipartite and directed networks [J]. Physical Review E, 2007, 76(3): 036102. CrossRef
  24. LEHMANN S, SCHWARTZ M, HANSEN L K. Biclique communities [J]. Physical Review E, 2008, 78(1): 016108. CrossRef
  25. SUN J, FALOUTSOS C, PAPADIMITRIOU S, YU P. GraphScope: Parameter-free mining of large time-evolving graphs [C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 687-96. CrossRef
  26. PAPADIMITRIOU S, SUN J, FALOUTSOS C, YU P. Hierarchical, parameter-free community discovery [C]// Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin: Springer-Verlag, 2008: 170-87. CrossRef
  27. ROSEN K H. Discrete mathematics and its applications [M]. 4th edition. Boston: WCB/McGraw-Hill, 1999.
  28. GIRVAN M, NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-826. CrossRef
  29. SIPSER M. Introduction to the theory of computation [M]. Boston: PWS Publishing Company, 1997.
  30. ASHLOCK D. Evolutionary computation for modeling and optimization [M]. New York: Springer, 2005.
  31. XU K K, LIU Y T, TANG R, ZUO J, ZHU J, TANG C J. A novel method for real parameter optimization based on gene expression programming [J]. Applies Soft Computing, 2009, 9(2): 725-37. CrossRef
  32. DAVIS A, GARDNER B B, GARDNER M R. Deep south [M]. Chicago: University of Chicago Press, 1941.
  33. FREEMAN L. Dynamic social network modeling and analysis [M]. Washington: The National Academies Press, 2003.
  
• 作者单位：Kai-kuo Xu (1)
  Chun-qiu Zeng (2)
  Chang-an Yuan (3)
  Chuan Li (4)
  Chang-jie Tang (4)
  
  1. College of Computer Science & Technology, Chengdu University of Information Technology, Chengdu, 610225, China
  2. School of Computing and Information Sciences, Florida International University, Miami, 33199, USA
  3. Guangxi Teachers Education University, Nanning, 530001, China
  4. School of Computer Science, Sichuan University, Chengdu, 610065, China
  
• ISSN：2227-5223

文摘

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.