Quantitative function and algorithm for community detection in bipartite networks

doi:10.1016/j.ins.2016.07.024

CSpace > 应用数学研究所

	Quantitative function and algorithm for community detection in bipartite networks
	Li, Zhenping 1; Wang, Rui-Sheng 2; Zhang, Shihua3 ; Zhang, Xiang-Sun3
	2016-11-01
发表期刊	INFORMATION SCIENCES
ISSN	0020-0255
卷号	367 页码:874-889
摘要	Community detection in complex networks is a topic of high interest in many scientific fields. A bipartite network is a special type of complex network whose nodes are decomposed into two disjoint sets such that no two nodes within the same set are adjacent. Many relationships in real-world systems can be represented by a bipartite network, such as predator-prey relationships, plant-pollinator interactions, and drug-target interactions. While community detection in unipartite networks has been extensively studied in the past decade, identification of modules or communities in bipartite networks is still in its early stage. Several quantitative functions have been developed for evaluating the quality of bipartite network divisions, however, these functions were designed based on null model comparisons and thus are subject to certain resolution limits. In this paper, we propose a new quantitative function called bipartite partition density for community detection in bipartite networks, and use some network examples to demonstrate that this quantitative function is superior to the widely used Barber's bipartite modularity and other functions. Based on the bipartite partition density, the bipartite network community detection problem is formulated into an integer nonlinear programming model in which a bipartite network can be partitioned into reasonable overlapping communities by maximizing the quantitative function. We further develop a heuristic adapted label propagation algorithm (BiLPA) to optimize the bipartite partition density in large-scale bipartite networks. BiLPA is efficient and does not require any prior knowledge about the number of communities in the networks. We conduct extensive experiments on simulated and real-world networks and demonstrate that BiLPA can successfully identify the community structures of bipartite networks. (C) 2016 Elsevier Inc. All rights reserved.
关键词	Bipartite network Community Quantitative function Integer programming Label propagation algorithm
DOI	10.1016/j.ins.2016.07.024
语种	英语
资助项目	National Natural Science Foundation of China[61379092] ; National Natural Science Foundation of China[61422309] ; National Natural Science Foundation of China[71540028] ; National Natural Science Foundation of China[11131009] ; Foundation for Members of Youth Innovation Promotion Association, CAS ; Outstanding Young Scientist Program of CAS ; Key Laboratory of Random Complex Structures and Data Science at CAS ; Beijing High Level Innovation and Entrepreneurship Talent Support Program-Famous Teacher, Beijing Key Laboratory[BZ0211] ; Beijing Intelligent Logistics System Collaborative Innovation Center
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000382794400052
出版者	ELSEVIER SCIENCE INC
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/23569
专题	应用数学研究所
通讯作者	Zhang, Shihua; Zhang, Xiang-Sun
作者单位	1.Beijing Wuzi Univ, Sch Informat, Beijing, Peoples R China 2.Harvard Med Sch, Brigham & Womens Hosp, Dept Med, Boston, MA USA 3.Acad Math & Syst Sci, CAS, Natl Ctr Math & Interdisciplinary Sci, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Li, Zhenping,Wang, Rui-Sheng,Zhang, Shihua,et al. Quantitative function and algorithm for community detection in bipartite networks[J]. INFORMATION SCIENCES,2016,367:874-889.
APA	Li, Zhenping,Wang, Rui-Sheng,Zhang, Shihua,&Zhang, Xiang-Sun.(2016).Quantitative function and algorithm for community detection in bipartite networks.INFORMATION SCIENCES,367,874-889.
MLA	Li, Zhenping,et al."Quantitative function and algorithm for community detection in bipartite networks".INFORMATION SCIENCES 367(2016):874-889.