ITP OpenIR  > 理论物理所2016年知识产出
Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks
Ghasemian, A; Zhang, P; Clauset, A; Moore, C; Peel, L; Ghasemian, A (reprint author), Univ Colorado, Dept Comp Sci, Boulder, CO 80309 USA.
2016
发表期刊PHYSICAL REVIEW X
卷号6期号:3页码:31005
文章类型Article
摘要The detection of communities within a dynamic network is a common means for obtaining a coarse-grained view of a complex system and for investigating its underlying processes. While a number of methods have been proposed in the machine learning and physics literature, we lack a theoretical analysis of their strengths and weaknesses, or of the ultimate limits on when communities can be detected. Here, we study the fundamental limits of detecting community structure in dynamic networks. Specifically, we analyze the limits of detectability for a dynamic stochastic block model where nodes change their community memberships over time, but where edges are generated independently at each time step. Using the cavity method, we derive a precise detectability threshold as a function of the rate of change and the strength of the communities. Below this sharp threshold, we claim that no efficient algorithm can identify the communities better than chance. We then give two algorithms that are optimal in the sense that they succeed all the way down to this threshold. The first uses belief propagation, which gives asymptotically optimal accuracy, and the second is a fast spectral clustering algorithm, based on linearizing the belief propagation equations. These results extend our understanding of the limits of community detection in an important direction, and introduce new mathematical tools for similar extensions to networks with other types of auxiliary information.
学科领域Physics
资助者BioFrontiers IT [NIH 1S10OD012300] ; BioFrontiers IT [NIH 1S10OD012300] ; National Science Foundation [IIS-1452718] ; National Science Foundation [IIS-1452718] ; U.S. Air Force Office of Scientific Research (AFOSR) [FA9550-12-1-0432] ; U.S. Air Force Office of Scientific Research (AFOSR) [FA9550-12-1-0432] ; Defense Advanced Research Projects Agency (DARPA) ; Defense Advanced Research Projects Agency (DARPA) ; Army Research Office (ARO) [W911NF-12-R-0012] ; Army Research Office (ARO) [W911NF-12-R-0012] ; John Templeton Foundation ; John Templeton Foundation ; BioFrontiers IT [NIH 1S10OD012300] ; BioFrontiers IT [NIH 1S10OD012300] ; National Science Foundation [IIS-1452718] ; National Science Foundation [IIS-1452718] ; U.S. Air Force Office of Scientific Research (AFOSR) [FA9550-12-1-0432] ; U.S. Air Force Office of Scientific Research (AFOSR) [FA9550-12-1-0432] ; Defense Advanced Research Projects Agency (DARPA) ; Defense Advanced Research Projects Agency (DARPA) ; Army Research Office (ARO) [W911NF-12-R-0012] ; Army Research Office (ARO) [W911NF-12-R-0012] ; John Templeton Foundation ; John Templeton Foundation
DOIhttp://dx.doi.org/10.1103/PhysRevX.6.031005
关键词[WOS]STOCHASTIC BLOCKMODELS ; RECONSTRUCTION ; PREDICTION ; MODEL
收录类别SCI
语种英语
资助者BioFrontiers IT [NIH 1S10OD012300] ; BioFrontiers IT [NIH 1S10OD012300] ; National Science Foundation [IIS-1452718] ; National Science Foundation [IIS-1452718] ; U.S. Air Force Office of Scientific Research (AFOSR) [FA9550-12-1-0432] ; U.S. Air Force Office of Scientific Research (AFOSR) [FA9550-12-1-0432] ; Defense Advanced Research Projects Agency (DARPA) ; Defense Advanced Research Projects Agency (DARPA) ; Army Research Office (ARO) [W911NF-12-R-0012] ; Army Research Office (ARO) [W911NF-12-R-0012] ; John Templeton Foundation ; John Templeton Foundation ; BioFrontiers IT [NIH 1S10OD012300] ; BioFrontiers IT [NIH 1S10OD012300] ; National Science Foundation [IIS-1452718] ; National Science Foundation [IIS-1452718] ; U.S. Air Force Office of Scientific Research (AFOSR) [FA9550-12-1-0432] ; U.S. Air Force Office of Scientific Research (AFOSR) [FA9550-12-1-0432] ; Defense Advanced Research Projects Agency (DARPA) ; Defense Advanced Research Projects Agency (DARPA) ; Army Research Office (ARO) [W911NF-12-R-0012] ; Army Research Office (ARO) [W911NF-12-R-0012] ; John Templeton Foundation ; John Templeton Foundation
WOS类目Physics, Multidisciplinary
引用统计
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/21590
专题理论物理所2016年知识产出
通讯作者Ghasemian, A (reprint author), Univ Colorado, Dept Comp Sci, Boulder, CO 80309 USA.
推荐引用方式
GB/T 7714
Ghasemian, A,Zhang, P,Clauset, A,et al. Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks[J]. PHYSICAL REVIEW X,2016,6(3):31005.
APA Ghasemian, A,Zhang, P,Clauset, A,Moore, C,Peel, L,&Ghasemian, A .(2016).Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks.PHYSICAL REVIEW X,6(3),31005.
MLA Ghasemian, A,et al."Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks".PHYSICAL REVIEW X 6.3(2016):31005.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Detectability thresh(1231KB) 开放获取--请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Ghasemian, A]的文章
[Zhang, P]的文章
[Clauset, A]的文章
百度学术
百度学术中相似的文章
[Ghasemian, A]的文章
[Zhang, P]的文章
[Clauset, A]的文章
必应学术
必应学术中相似的文章
[Ghasemian, A]的文章
[Zhang, P]的文章
[Clauset, A]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。