下载  >  开发技术  >  其它  > 论文研究-Resolution limit in community detection for an information-theoretic method.pdf

论文研究-Resolution limit in community detection for an information-theoretic method.pdf 评分

一种基于信息理论的社团识别方法的分辨极限问题研究,孙鹏岗,,分辨极限对于社团识别非常重要,同时也对社团检测方法提出了新的挑战。众所周知,模块优化算法暴露出严重的分辨极限问题在于多个
国武技论文在线 http:/www.paper.edu.cn Given is an unweighted and undirected network with nodes and links, which can be described by the adjacency matrix A=: where了,∈{l,2,…,-1,},=1, if there is a link between node and nodc 0 otherwise is the description for communities. a is the community assignment vector and ∈{1,2 1,. M=M( a) is the community matrix that shows the connection of communities given by a. Community and community have and nodes respectively and with edges betwecn them 231 lI :,M= (2) 90 In order to find the best assignment for a, Rosvall and Bergstrom [2 maximized the mutual in formation bctwccn the original nctwork, and its encoded fashion, over all possible assignments, a =arg max (x; Y The mutual information (:=()-(/=()-( where ndicates the information of and (/)= is the information of given. For acquiring the maximal(;,()must be minimized Rosvall and Bergstrom [23] mentioned that it is equivalent to finding an assignment vector so that the candidates for estimating are as small as possible Given assigns nodes to communities. (-1)/2 100 (=log where the binomial coefficients are in parentheses. The first product shows the number of different communities constructed by nodes and edges for each of the binomial coefficients. The 3 国武技论文在线 http:/www.paper.edu.cn number of different ways community and community linked with each other for each of the 1)/2 binomial coefficients are in the second product 23) 105 Rosvall and Bergstrom (25 also mentioned that minimizing h(z) works well, but only as long as the total number of communitics, m is known beforehand. Otherwise, the optimal valuc of H(z) becomes a strictly decrcasing function of m when the number of communitics is unknown for a given network. Thus, simply minimizing the entropy will lead to the trivial partition, and the becomes simply the adjacency matrix of the nctwork 251. Rosvall and Bergstrom 2]also showed that 110 only with the full description length can the method balance overfitting and underfitting the data for the network. In the method, Rosvall and Bergstrom indicated 2 that the full description length, the one of the model plus the one of the network given the model, L(Y)+L(XY, or L()+ H(Z)(L(XY)=H(Z)) should be minimized. L(Y)is the description length of the model itself, and L(XY)is the description length of the network for the fitted model. Rosvall and Bergstrom [23 employed the minimum 115 description length(MDL) principle 26, 27 in their method for community detection, when the number of communities is unknown beforehand. In addition, Peixoto in his recent work 25 generalized the MDL principle and applied it on stochastic block model to accommodate an arbitrarily large number of communities, and to obtain general bounds on the detectability of arbitrary community structures. He also showed the maximum number of detectable blocks scales as based on MDl principle. where 120 is the number of nodes in the network 2 Resolution limit for information-theoretic method n this section, we will discuss the resolution limit for the objective function, H(Z) in the information-theoretic method when the number of communities is known in advance. and the resolution limit for the objective function, L(Y)+H(Z) in the information-theoretic method whe 125 the number of communities is unknown beforehand 2. 1 Resolution limit for H(z For casy undcrstanding, we rewrite ( by thc following cquation (-1)/2 2 4 国武技论文在线 http:/www.paper.edu.cn 130 (2)n where a partition for V∈ l,2 is a subgraph induced by Hcrcin, wc first give a simplc thcorctic proof to show that ()is a rcsolution-limit-frcc 135 objective function in the information-theoretic method based on the discussion of frag and van Dooren - when the number of communities is known in advance, and then the test on the examples of fortunato and Barthelemy [i7 is showed later Given ()indicates that a partition =i 1525… ∈ for a graph optimal on the object function, if VE, then (<(), where is the set of 140 partitions for [24], and-(), otherwise Assume ()[24] Givcn 'is the induccd subgraph of by and. ( < 145 ∪'( by additivity)24 )+(') This inequality contradicts with ().Hencc, l50 After a simple proof has given, we further test ()on the same examples from Fortunato and Barthelemy Ill\ that the modularity optimization ca The following demonstrations are benefited from y an not correctly uncover the communities Firstly, we analyze the network mentioned by Fortunato and Barthelemy in Fig. 2(a)that can be partitioned into three or more communities. We show that minimizing ( can correctl reveal the communities in Fig. 2(a) 国武技论文在线 http:/www.paper.edu.cn k-clique GR-E't n 0 l2 (a) Fig. 2 Illustration examples. (a) A network is partitioned into three or more communities. The two communities, and on the left are denoted by circles, the rest of the network the oval on the right are with.. nodes and inks respectively; links are 160 bctwccn and links arc bctwccn and links arc bctwccn d .(b)A clique is classified into communities with nodes respectively 0,1, 2 are with 0,1, 2 nodes and 0,1,2 links respectively, and links are between an links are between and links are betweer an Here. we consider 165 two partitions 0,1,2and 0,152f anc are seen as separate communities, In '=1 0, (1, 2, and 2 are considered as a single community l)/2 (1-1)/2 (-1)/21(0(1+2)(1+2) 1)/2 g (0-1)/2 0 1(1-1)/2 (2-1)/2 170 (o-1)/2(0(1+2)(1+2)(1+2-1)/2 1).(02)(1-1)2.12 2 0(112 (1+2)(1+2-1)/2 + 国武技论文在线 http:/www.paper.edu.cn 1(1-1)/2 1)/2 1)/2+12+2(2-1)/ Based on /: where≥ Whe e that indicates each is a complete graph 01 1(1-1)/2)(12)(2(2-1)/2 175 01+021.((1-1)/2+12+2(2-1)2 (0-1)/2 1)/2 (2-1)/2 0(o-1)/2 0(1+2)(1+2)(1+2- (o-1)/2 02)(1(1-1)/2 12 2(2-1)/2 (1+21+2-1)/2 112 0(o-1)/2 (1-1)/2 (2-1)2 2 1)/2(0(1+2)(1+2 1)/2 180 Og 0(o-1)/2)(/o 1(1-1)/2)(12)(2(2-1)/2 g 0(o-1)/2 g (…)(*x+ 0 )≤0 )≤() 185 Minimizing can not merge d Into a single group Secondly, we prove whether minimizing ()can partition a clique into several parts(see Fig. 2(b). We show that minimizing ()can not classify a clique into some subgroups in Fig 2(b) 国武技论文在线 http:/www.paper.edu.cn k-clique 1 I k-clique I k-eliyue K-clie l-clique [k-tlique k-cHa i k-clique k-clique [k-clique Gt-1 k-clique A-clio A-clit K-clique r k-clique「 迎uc k-clique p-eliqu GAit A-clique k-clique g-clique H 4-clique G/t23 p-clique k-cliqu A-clique k-cliqjue厂 (d 190 Fig 3 Schematic cxamples. (a),(b) and(c)A nctwork with -cliques linked by a singlc cdgc is partitioned into communities with nodes respectively.(d) A network is made out oftwo -cliques and two -cliques Given a -clique can be classified into several subgroups (2≤≤,≥3). The number of nodes in 195 respectively, 1+2+,,+i+ ≥1,=1,2 denotes the partition that the -clique is considered as a single community, and indicates the partition that the -clique is partitioned into subgroups (-1)/2 ("-)=2()=∑og(-/2) 0 8 国武技论文在线 http:/www.paper.edu.cn 200 ()≤(1) Thcrcforc, minimizing ( can not partition a clique into several parts Thirdly, we further prove ( on the examples lrom Fortunato and Bartheleny (177 3. Fig 3(a)is a network with -cliques linked by a single edge to form a circle. Obviously, each 205 -clique is a community, but maximizing classifies two or more -cliques into a single group 7 We show that minimizing ()can correctly detect each clique as one community in Fig 3(a) ……∵…2-2·2m-12 2 Z={2;z1, t, (k-cliques) Fig 4 Illustration of correspondence between d ane Given the nctwork in Fig. 3(a) can be divided into communities, 1,2,. 210 consecutive -cliques respectively, -1 ≥1,=1,2, is used to denote the partition that each -clique is a community, and to denote the partition that -cliques are divided into communities )=∑() (-1)/2 215 (-1)/2八1 g ∑ (-1)/2 g (-1)/2+ For a one-to-one correspondence with we rewrite as(see f 220 ()=∑(') ∑( (2)=2(), and(')is the sum of consecutive -cliques in ' that also have a one-to-one correspondence with (see Fig. 4). Here, we only need to proof that 9 国武技论文在线 http:/www.paper.edu.cn VE, 2,,l,,()<(). We use mathematical induction to prove it ()=()( scc Fig.3(a) (ii)If =2, then(see Fig. 3(b) (-1)/2 Og (2-1))(22 2g, (-1) 2 +1 23 )(2-1) (-1)/2 (-1)/2 )=log (-1)/2八(1 1)/2八(1 (2-+1)!(2-1)! (22-)(22--1)…(2+1)( (22-)(2 1)…(2+2)(2+1) 235 (2-1/)(2-1/-1/2)…(1+2/)(1+1/ (1-1/+1/2)(1-1/)…(3/2)(1/2) (2-1/)>(2-1/-1/2)>…>(1+2/2)>(1+1/2)>1 1>(1-1/+1/2)>(1-1/)>…>3/2>1/2 (2-1/)(2-1/-1/)…(1+2/)(1+1 240 +1(1-1/+1/2)(1-1/)…(3/2)(1/2)>1 1(2-1/)2-1/-1/2)…(1+2/2)1+1/2) (2 )! 2 (2-+1)!(2-1) +1 10

...展开详情
所需积分/C币:6 上传时间:2019-08-18 资源大小:553KB
举报 举报 收藏 收藏
分享 分享
知识图谱构建技术综述

知识图谱构建技术综述 !!!!--!!!!!!! 学位论文

立即下载
KCFinder(CKEditor的文件管理器) v2.5.1

KCFinder 跟 CKFinder 类似,是 CKEditor 的一个开源文件管理器插件,通过该插件可上传和对包括图片、Flash动画以及其他文件进行你个浏览和管理。KCFinder 支持简体中文。KCFinder Features:01 Ajax engine with JSON responses02 Select multiple files with the Ctrl/Command key03 Download multiple files or a folder as single ZIP file04 Clipboard for copying and moving mult

立即下载
VGA_Display_Test1080P.zip

DE2-115 cycloneIV EP4CE115F29C7可以直接编译下载,实现VGA显示(多个分辨率:640*480—800*600—720P—1280*960—1440*900—1080P等等) 内附word说明如何修改程序实现不同分辨率 根文件源码来自于CarzyBird大神!

立即下载
ModbusTCP/RTU网关设计

基于UIP协议栈,实现MODBUS联网,可参考本文档资料,有MODBUS协议介绍

立即下载
html+css+js制作的一个动态的新年贺卡

该代码是http://blog.csdn.net/qq_29656961/article/details/78155792博客里面的代码,代码里面有要用到的图片资源和音乐资源。

立即下载
iCopy解码软件v1.0.1.7.exe

解ic,id,hid卡密码破解ic,id,hid卡密码破解ic,id,hid破解ic,id,hid卡破解ic,id,hid卡密码密码卡密码破解ic,id,hid卡...

立即下载
分布式服务框架原理与实践(高清完整版)

第1章应用架构演进1 1.1传统垂直应用架构2 1.1.1垂直应用架构介绍2 1.1.2垂直应用架构面临的挑战4 1.2RPC架构6 1.2.1RPC框架原理6 1.2.2最简单的RPC框架实现8 1.2.3业界主流RPC框架14 1.2.4RPC框架面临的挑战17 1.3SOA服务化架构18 1.3.1面向服务设计的原则18 1.3.2服务治理19 1.4微服务架构21 1.4.1什么是微服务21 1.4.2微服务架构对比SOA22 1.5总结23 第2章分布式服务框架入门25 2.1分布式服务框架诞生背景26 2.1.1应用从集中式走向分布式.26?

立即下载
Camtasia 9安装及破解方法绝对有效

附件中注册方法亲测有效,加以整理与大家共享。 由于附件大于60m传不上去,另附Camtasia 9百度云下载地址。免费自取 链接:http://pan.baidu.com/s/1kVABnhH 密码:xees

立即下载
电磁场与电磁波第四版谢处方 PDF

电磁场与电磁波第四版谢处方 (清晰版),做天线设计的可以作为参考。

立即下载
压缩包爆破解密工具(7z、rar、zip)

压缩包内包含三个工具,分别可以用来爆破解密7z压缩包、rar压缩包和zip压缩包。

立即下载
source insight 4.0.0087 注册机序列号Patched(2017/10/17)

最新的sourceinsight4.0.0087和谐license及和谐文件。真正的4087版本,使用附件中的license文件,替换sourceinsight4.exe

立即下载
Java项目经验汇总(简历项目素材)

Java项目经验汇总(简历项目素材)

立即下载
支付宝转账demo

支付宝单笔转账,实现提现功能(内有demo实例,望大家多多提意见)

立即下载
新开普身份证读卡器驱动

安装新开普身份证读卡器驱动后,可以读取身份证信息,

立即下载
算法第四版 高清完整中文版PDF

《算法 第4版 》是Sedgewick之巨著 与高德纳TAOCP一脉相承 是算法领域经典的参考书 涵盖所有程序员必须掌握的50种算法 全面介绍了关于算法和数据结构的必备知识 并特别针对排序 搜索 图处理和字符串处理进行了论述 第4版具体给出了每位程序员应知应会的50个算法 提供了实际代码 而且这些Java代码实现采用了模块化的编程风格 读者可以方便地加以改造

立即下载
最新的微信小程序源码

最新的微信小程序源码70多个很多行业都有加后台

立即下载
数据库系统概念第六版答案(最全)

史上最全的数据库系统概念第六版(机械工业出版社)课本答案

立即下载
柏林语音情感数据库完整版

这是柏林语音情感数据库完整版,包括音频和标签,适合从事语音识别的研究者进行语音情感识别。

立即下载
高等数学第七版(同济大学)下册pdf

高等数学第七版(同济大学)下册教材pdf (PS:高等数学第七版上下册均有,因上传文件容量有限,因此分为两次上传,请有需要上册的朋友点开我的资源下载页进行下载)

立即下载
老R4通用内核

很久以来老R4没有下载了,此通用格式给需要的朋友!谢谢

立即下载