文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 复杂网络社区结构发现算法概述
侵权投诉

复杂网络社区结构发现算法概述

算法分析

篇

复杂网络社区结构发现算法概述 杨泽俊 1, 2何柳 a

( 1 .三峡大学湖北宜昌 4 4 3 0 0 0;2 .湖北三峡职业技术学院湖北宜昌 4 4 3 0 0 0; 3 .三峡旅游职业技术学院湖北宜昌 4 4 3 0 0 0 ) 摘要:分析了一些经典的复杂网络社区结构的发现算法,希望对社区发现问题的进一步研究及若干问题的早日解决起到一定的作业。 关键词:复杂网络社区结构中图分类号: T P 3 文献标识码: A

文章编号: 1 0 0 7— 9 4 1 6 ( 2 0 1 3 ) 0 3— 0 1 4 5一 O 1

1引言 复杂网络[ 1堤现实世界中复杂系统的一种抽象表现形式,网络中的节点是复杂系统中的个体,节点之间的边则是系统中个体之间按照某种规则而自然形成或人为构造的一种关系。网络节点被划分成若干组,使得组内节点之间的连接比较稠密,而不同组节点之间的连接则比较稀少,这样的划分结果被定义为复杂网络的社区结构[ 2 1通过对复杂网络社区结构的研究,可以将复杂网络社区结构的研究理论成果应用到具体问题当中去,如可以通过社区结构发现资源分布、病毒的传播等。 。

较小,而不同社区的节点对介数较大,为此可以比较好的划分社区。

设网络矩阵中对角线上各元素之和为 T r e

巴 l。该矩阵给出

了网络中连接某一个社区内部各节点的边在所有边的数目中所占比例,定义每行 (或者列)中各元素之和为 1;/ i 性的衡量标准:

勺,它表示与第价

社区中的节点相连的边在所有边中所占的比例,用下式来定义模块 乙一 i 2 ) " r e一 0上式的意义是:矩阵网 。

2基于 L a p l a c e图特征值的谱二分法【 3】 令G是一个具有n个节点的无向图, G的L a p l a c e矩阵L是一个 n X n的对称矩阵,它的对角线元素uj是节点i的度,表示节点i和节点 j的连接情况,当i和j之间有边相连时,则L i j=一1,否则 L i j= 0。显然, L每一行的和以及每一列的和均为0,因而,向量l= ( 1, 1, 1, 1 )是L的相应于特征值0的特征向量。可以知道,此时L存在g个与特征值o N应的特征向量, k= l, 2, L, g,其中, v ( k )的对应

于分支G k的分量为 1,而其余分量为0。 因为对称矩阵的任意2个特征值所对应的特征向量相互正交, 所以L a p l a c e矩阵L的任意对应于非零特征值的特征向量均正交于向量 L= ( 1, 1, l, 1 ),以此所有非零特征值的特征向量必须具有正分 量和负分量。如果2个子图间连接很少,则将存在一个特征向量,它的特征值近似于0;它的特征向量的正分量对应一个子图,负分量对应另一个子图。 所以我们可以通过观察第二最小的特征值所对应的特征向量,依据特征值元素的正负将一个网络分解成2个社区,这就是谱二分法。

络中连接两个同种类型的节点的边的比例减去在同样的社区结构下任意连接这两个节点的边的比例的期望值。如果社团内部边的比例不大于任意连接时的期望值,则有Q=O。 Q的上限为 Q=I,而Q越接近这个值,则说明社团结构越明显。 G N算法中,如果计算关于有m个节点和n条边的网络的所有边的介数则需O ( mn )的时间。每一次删除边,都要重新计算一次边介数,所有整个算法的时间复杂度在最坏的情况是O( m n )。

5贪婪算法

贪婪算法与上面算法的共同之处在于都是以最大化Q函数值为目 标,区别是最大化的途径不同。贪婪算的过程为: ( 1翮始时将网络中的每1个顶点都视为 1个社团,每个社团内只有 1个顶点。 c 2 )两两合并社团,并计算社团合并所产生的Q值的变化量:△Q=,+ e - 2 a, a j= 2 (一口 口, )选择使得Q值增加最大的合并方式进行。计算Q值变化时,只需考虑存在连边的网络社团对。当网络中包含n条边时,这步算法的复杂度为 O( n )。网络社团合并后一定会对e矩阵产生影响,所以将合并的两个社团所对应的行和列相加,对e i j进行更新。 ( 3 )重复步骤( 2 )的操作, 不断对社团进行合并,一直到所有顶点被凝聚到一个社团为止。上述的操作最多进行n一 1次。这种方法将复杂网络中的社团用树状图 3W H算法的形式表现,使得Q函数值最大的社团划分方式就是网络的最优划 在明确知道社团数目的情况下, Wu和 Hu b e r ma n提出了基于分结果。电阻网络电压谱的快速谱分割法。利用此算法不仅可以求出

复杂网参考文献络的社团结构,还可以在不考虑整个复杂网络扩大社团结构的情况[ 1] W W Z a c h a r y .An i n f o r m a t i o n f l o w J o u r n a l o f A n t h r o p o l o gi c a l 下,寻找一个已知节点所在的整个社团。 令图G= ( v, E )可以分为两个社团G1和G 2,且已知节点M和N分别属于这两个社团。令节点M为源节点,电压值为 1,节点N为终节点,电压值为0。此时,网络中的每条边都视为一个阻值为l的电阻。 复杂网络就可以看成一个电阻网络,可以利用基尔霍夫定理求各个几点的电压值。然后,选取一个电压阈值V ( O<V<I )。若节点i的电压值V i>V,认为它属于源节点M所在的社团,反之则为终结点N所在的社团。可以利用谱线图来记录电压值:在0~l的范围内,将电压值从大到小进行排列,然后用不同位置的谱线图来记录电压值。然后选取某个阈值,认为该阈值左边的线相应的节点属于一个社团,而右边的那些节点就属于另一个社团。 R e s e a r c h . m o d e l f o r c o n f l i c t a n d f i s s i o n i n s m a l l g r o u p s . 1 9 7 7。 3 3

( 4 ): 4 5 2—4 7 3 .

[ 2] W W Z a c h a r y .A n i n f o r ma t i o n f l o w J o u r n a l o f A n t h r O p O1 O g 1 c a] R e s e a r c h . m o d e l f o r c o n f l i c t a n d f i s s i o n i n s m a l l g r o u p s . 1 9 7 7。 3 3

( 4 ): 4 5 2 -4 7 3 .

[ 3]汪小帆,李翔,陈关荣.复杂网络理论及其应用[ H] .北京:清华大学 出版社。 2 0 0 6 . [ 4] Gi r v a n M . N e wm a n M E J.C o mmu n i t y s t r u c t u r e 1 n s o c i a 1 a n d b i o l o g i c a l n e t w o r k s[ J] . P r o c N a t l A c a d S c i U S A . 2 0 0 2。 9 9: 7 8 21. 7 8 2 6 .

[ 5] N e w m a n M E] . F a s t

a l g o r i t h m f o r d e t e c t i n g c o m mu n i t y s t r u t. t u r e i n n e t w o r k s[ J] . P r o c N a t l A c a d S c i, 2 0 0 1, 9 9: 7 8 2 1. 7 8 2 6 .

4GN算法 G N算法[ 4 1的思想是不断从网络中移除介数最大的边,边的介数是指通过该边的最短路径的数目。因为同一社区内的节点对介数

复杂网络社区结构发现算法概述

第1页

你可能喜欢

  • 网络现状
  • 网络基础
  • 网络动力学
  • 维基百科
  • 自动控制基础知识

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email