网络社区划分算法.doc

《网络社区划分算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、下载可编辑网络社区划分算法目录·1 简介·2 构建一个点击流网络·3 网络社区划分的两种主要思路：拓扑分析和流分析·4 拓扑分析o4.1 计算网络的模块化程度Q-Modularityo4.2 计算网络的连边紧密度Edgebetweennesso4.3 计算网络拉普拉斯矩阵的特征向量Leadingeigenvectoro4.4 通过fastgreedy方法搜索网络模块化程度Q-Modularity的最大值o4.5 通过multilevel方法搜索网络模块化程度Q-Modularity的最大值·5 流分析o5.1 

2、随机游走算法WalkTrapo5.2 标签扩散算法labelpropagationo5.3 流编码算法theMapEquationo5.4 流层级算法Role-basedSimilarity·6 总结[]简介.专业.整理.下载可编辑使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如

3、，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。[]构建一个点击流网络假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（uservisit）排名前V的资源，得到节点集合

4、V

5、，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于

6、V

7、的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成v

8、i(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天内的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到

9、M

10、个不同的边，每条边上都带有权重信息。这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。[]网络社区划分的两种主要思路：拓扑分析和流分析社区划分的算法比较多，但我个人认为大致可以分为两大类：拓扑分析和流分析。前者一般适用于无向无权网络

11、，思路是社区内部的连边密度要高于社区间。后者适用于有向有权网络，思路是发现在网络的某种流动（物质、能量、信息）中形成的社区结构。这两种分析各有特点，具体应用取决于网络数据本身描述的对象和研究者想要获得的信息。.专业.整理.下载可编辑我们可以将已知的一些算法归入这两类：算法优化目标计算复杂度适用情况局限拓扑分析QModularity最大化Q-modularityV

12、^2无向无权多分量不适用小网络Edge-Betweenness最小化社区间连边的betweennessV

13、*

14、E

15、^2有向有权多分量慢LeadingE

16、igenvector对拉普拉斯矩阵第二小特征根对应的特征向量聚类V

17、^2+

18、E

19、无向无权多分量FastGreedy使用社区合并算法来快速搜索最大Q-modularityE

20、*log(

21、V

22、)无向有权多分量不适用小网络.专业.整理.下载可编辑MultiLevel使用社区展开算法来快速搜索最大Q-modularityV

23、无向有权多分量不适用小网络流分析WalkTrap最大化社区间的流距离E

24、*

25、V

26、^2无向有权单分量LabelPropagation每个节点取邻居中最流行的标签，迭代式收敛V

27、+

28、E

29、无向有权单分量结

30、果不稳定Infomap最小化随机流的编码长度V

31、*(

32、V

33、+

34、E

35、)有向有权单分量Role-basedcommunity划分出在流中地位类似的节点V

36、^3有向有权单分量结果不稳定上表中的分量（component）指在网络中的独立“团块”。有向网络里，分量有强弱之分，强分量（strongcomponent）中任意一个节点都可到达另外一个节点，弱分量（weakcomponent）中如果忽略连边方向，则构成强分量。无向网里分量没有强弱之分。在网络中识别强分量的算法有Kosaraju算法，Tarjan算法及其变形Gab

37、ow算法等。在这里不展开叙述。接下来，我们逐一讨论拓扑分析和流分析中的各种算法的具体思路。[]拓扑分析[]计算网络的模块化程度Q-Modularity.专业.整理.下载可编辑Q-Modularity是一个定义在[-0.5,1)区间内的指标，其算法是对于某一种社区结构，考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望，说明节点越有集中在某些社区内的趋势，即网络的模块化结构越明显