论文部分内容阅读
摘要：社团发现算法是分析研究复杂网络结构的有效方法之一，针对该问题，在分析节点相似度和网络拓扑结构的基础上，提出了一种基于节点相似度复杂网络社团发现算法，算法以模块密度函数和标准互信息作为社团的评价参数对复杂网络实施有效划分。人工网络和真实网络上的实验结果表明，算法能够准确的发现复杂网络中的社区结构。
关键词： 社团发现； 节点相似； 模块密度； 复杂网络
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）08-0042-03
Abstract：Community detection is one of the effective methods for analyzing the structure of complex network. In this paper， the node similarity and topology of network is analyzed， a new community detection algorithm in complex network based on node similarity is proposed. The modularity density and normalized mutual information are chosen to be the evaluation parameters to detect the community structure. Experimental results on both artificial network and real world networks show the algorithm can detect the structure of community complex networks.
Key words：community detection； node similarity； modularity density； complex network
1 引言
社團结构的发现已经成为复杂网络研究方向中重要的研究方向，社团结构是复杂网络具有共同性质的节点的集合，在社团内部节点连接较为紧密，节点之间的相似度较高，具有一些的共同属性和相似的拓扑结构；而不同社团之间的连接则较为稠密，节点之间的相似性较低[1]。目前对于复杂网络的研究已经广泛的应用在社会网络、生物网络、通讯网络等的网络结构研究问题中，针对其中的社团结构的研究也已经成为了热点研究方向[2-6]。本文针对网络中节点相似度，构建了基于节点相似度的社团发现算法。
2 基于节点相似度的社团发现算法
2.1 相似度的定义
复杂网络中的连通图可以表示为G=（V，E），其中V是图中节点的集合，定义为V={v1， v2，…，vn}， n为网络中节点的数量，E是图中边的集合，表示为E={（vi，vj）| vi，vj∈V}，在一般的复杂网络定义中，边值定义为两个节点之间的物理距离，若两个节点之间没有连接，则边值定义为0，存在连接的话边值为实际距离。而为了分析基于用户相似度的网络，将边值设为两个节点的相似度值，两个节点的相似度越大，则连接这两个节点的边值也越大。
为了衡量两个节点之间的相似度，根据复杂网络的定义认为如果两个节点拥有较多的共同邻接节点，则它们的相似度应该较大；反之，而若它们之间的共同邻接节点较少，则相似度较小。设节点vi的邻接节点的集合为Ni，节点vj的邻接节点的集合为Nj，则它们所拥有的共同邻接节点的集合可以表示为Ni∩ Nj。则这两个节点的相似度可以定义为：
但是由于在复杂网络中存在着“富人俱乐部”特性，即在复杂网络中的度分布呈现出长尾性质，度较小的节点占据网络中的大多数，而这些度较小的节点也倾向于网络中少量存在的度较大的节点，这些度较大的节点会因为不断的吸引导致度更大[7]。考虑到这些“富人节点”的度较大，使得其他节点和它们的共同邻接节点数量较多，导致它们的相似度很高，从而对其他非“富人节点”之间的相似度进行干扰。为了解决上述定义，相似度定义为：
在公式（3）中使用对数函数对复杂网络中的“富人节点”与其他节点进行相似度计算后相似度值要明显大于其他普通节点之间的相似度值的现象进行抑制。而由于当|Ni∩ Nj|<1时，相似度值为负的情况，公式（3）在对数函数内部进行加一，这样保证了相似度的值为正的完备性。
2.2 模块密度定义
Newman等人在文献[8]中提出了模块度Q作为网络社区划分质量的评价参数，其公式定义为：
在公式中， eii是边所连接的两个节点均在社区Gi内的边占网络中所有边的比例，ai是边所连接的节点中至少有一个在社区Gi内的边占网络中所有边的比例。模块度函数可以反映社区结构的明显程度，社区结构越明显，则模块度函数值越大，反之社区结构越弱，模块度函数值越小。
使用模块度作为社团划分的评价参数存在着对于小社团结构无法正确发现的分辨率极限问题，所以目前也有很多对于模块度进行改进的研究。Fortunato等人在文献[9]中提出了使用模块密度作为社区划分的评价函数，其定义为：
其中L（Vi， Vi）表示某个社团内部的连接数量，而表示该社团与其他社团的连接数量，基于复杂网络的邻接矩阵A，它们分别可以表示为：
模块密度定义了所有子图平均内部连接率和所有子图与子图之间的平均外部连接率的差，反映了模块内部和模块之间的连接紧密程度。对于网络中的社团结构，其基础定义就是社团内部连接较为紧密而不同社团之间的连接较为稀疏。 2.3 算法描述
算法流程描述如下：
输入：无向网络图G=（V，E）
输出：网络G的社团结构
Step1：初始化网络社团结构，使得整个网络构成一个大型社团结构；
Step2：若网络中||V||=0或者||E||=0，则退出算法，否则计算每个节点对的相似度，并存于节点相似度矩阵中；
Step3：遍历节点相似度矩阵中的值，删除其中相似度最小的社團连接；
Step4：重复Step3直到社团连接数量小于阈值，形成一个终止的社团划分结果。
3 实验验证及分析
3.1 人工合成网络实验
为了验证算法的有效性，先使用Lancichinetti提出的基准网络对算法进行验证。Lancichinetti网络由128个节点组成，这些节点被划分为4个社团，每个社团包含32个节点，节点的平均度为16。该网络的构成可以通过混合参数γ进行调整，γ表示节点与该节点所属社区之外的所有社区之间的边数占该节点所有连接的百分数，所以γ越小则社团内部连接数较多，连接更为紧密，社区结构也就更加明显。随着混合参数的γ的增大，与其他社团的连接数量越多，社团结构也变得不明显，通常认为当γ=0.5时，社团结构已经较难进行识别。
实验根据Lancichinetti网络的规则，构造了γ取值范围为0到0.5的11个测试网络，对于每个测试网络运行算法20次，并记录社团划分结果。对于社团划分结果，使用标准互信息（Normalized Mutual Information）作为评价参数，标准互信息可以表示由算法发现的社区结构和真实社区结构之间的相似性，若两者完全一致，则标准互信息的值为1，反之，若完全不相似则为0。标准互信息公式定义为：
其中A代表真实网络的社团划分情况，CA表示真实网络中社团的数量，B表示算法得出的网络社团划分情况，CB表示由算法的得到的社团数量，Ci?表示邻接矩阵中第i行元素的和，C?j表示邻接矩阵中第j列元素的和。若使用算法得到的社团结构与真实网络的社团结构完全一致，则NMI（A，B）=1；反之若完全不一致则NMI（A，B）=0。实验结果如图1所示。
图1显示了γ取值不同时使用算法得出的NMI平均值的变化情况。随着混合参数γ的增加，NMI平均值逐渐减小，当γ=0.5时NMI平均值达到最小，而在γ≤0.35时NMI平均值均为1，即说明与真实网络的社团划分结果一致。从图1中可以看出，本文算法在混合参数γ增大的变化趋势中，相比于其他算法NMI平均值下降速度较慢，当γ≤0.35的情况下始终可以保持与真实社团结构一致。
3.2 真实网络数据实验
为了进一步验证算法的有效性，使用其他三个真实网络数据集来对算法进行评价：Zachery空手道俱乐部网络、美国大学橄榄球网络和球鼻海豚网络。Zachery空手道俱乐部网络是Zachery对一个空手道俱乐部观测得到的，网络中的节点代表俱乐部的成员，网络中的边数代表俱乐部成员之间的交流。网络的社区划分是分别由俱乐部管理者和俱乐部教练为核心的两个子网络。美国大学橄榄球网络表示美国大学橄榄球比赛2000年赛季第一分区的比赛日程安排表，网络中顶点表示球队，连接两个顶点的边表示这两个球队之间有比赛。这些球队被分为多个联盟，每一个球队平均和联盟内的球队进行了7场比赛，和联盟外的球队进行了4场比赛，因此具有较为明显的社区划分结构。球鼻海豚网络是由Lusseau通过7年时间观察生活在新西兰Doubtful Sound的62头海豚的行为编辑而成的社会网络，该网络之间的连接基于统计海豚之间有意义的频繁交往而建立起来的，62个节点根据交往的频繁程度被分为2组，即划分为2个社区。
对于每个真实网络，运行算法20次并保存社团划分结果，表1记录了每个真实网络的社团划分的社团数量和NMI平均值，图2-图4表示了社团划分结果的图形：
4 结论
本文针对复杂网络中的社团发现问题，基于节点的相似度构建了社团发现模型算法，通过使用人工合成网络进行实验并与其他算法进行对比，本文算法在社团结构不明显的情况下，仍然对社团结构具有一定的发现能力，证明了算法具有一定的优势。而通过真实网络数据的实验验证，证明了算法在真实的网络中的有效性。
参考文献：
[1] 刘大有，金弟，何东晓等.复杂网络中的社区结构算法综述[J].计算机研究与发展， 2013，50（10）： 2140-2154.
[2] Watts D J，Strogatz S H.Collective dynamics of ‘small-world’ networks[J].nature，1998， 393（6684）： 440-442.
[3] Girvanm，Newman M E J.Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America，2002，9 （12）：7821—7826.
[4] 张健沛，李泓波，杨静，等.基于拓扑势的网络社区结点重要度排序算法[J].哈尔滨工程大学学报，2012， 33（6）： 745-752.
[5] 程学旗，沈华伟.复杂网络的社区结构[J].复杂系统与复杂性科学，2011，8（1）： 57-70.
[6] 张健沛，李泓波，杨静.基于归属不确定性的变规模网络重叠社区识别[J].电子学报，2012， 40（12）： 2512.2518.
[7] 汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].清华大学出版社有限公司，2006.
[8] Newman M E J，Girvan M.Finding and evaluating community structure in networks[J]. Physical review E，2004，69（2）： 26-113.
[9] Fortunato S，Barthélemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences，2007，104（1）： 36-41.
[10] Lancichinetti，Andrea，Santo Fortunato，Filippo Radicchi.Benchmark graphs for testing community detection algorithms[J].Physical review E，2008（4）： 46-110.
关键词： 社团发现； 节点相似； 模块密度； 复杂网络
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）08-0042-03
Abstract：Community detection is one of the effective methods for analyzing the structure of complex network. In this paper， the node similarity and topology of network is analyzed， a new community detection algorithm in complex network based on node similarity is proposed. The modularity density and normalized mutual information are chosen to be the evaluation parameters to detect the community structure. Experimental results on both artificial network and real world networks show the algorithm can detect the structure of community complex networks.
Key words：community detection； node similarity； modularity density； complex network
1 引言
社團结构的发现已经成为复杂网络研究方向中重要的研究方向，社团结构是复杂网络具有共同性质的节点的集合，在社团内部节点连接较为紧密，节点之间的相似度较高，具有一些的共同属性和相似的拓扑结构；而不同社团之间的连接则较为稠密，节点之间的相似性较低[1]。目前对于复杂网络的研究已经广泛的应用在社会网络、生物网络、通讯网络等的网络结构研究问题中，针对其中的社团结构的研究也已经成为了热点研究方向[2-6]。本文针对网络中节点相似度，构建了基于节点相似度的社团发现算法。
2 基于节点相似度的社团发现算法
2.1 相似度的定义
复杂网络中的连通图可以表示为G=（V，E），其中V是图中节点的集合，定义为V={v1， v2，…，vn}， n为网络中节点的数量，E是图中边的集合，表示为E={（vi，vj）| vi，vj∈V}，在一般的复杂网络定义中，边值定义为两个节点之间的物理距离，若两个节点之间没有连接，则边值定义为0，存在连接的话边值为实际距离。而为了分析基于用户相似度的网络，将边值设为两个节点的相似度值，两个节点的相似度越大，则连接这两个节点的边值也越大。
为了衡量两个节点之间的相似度，根据复杂网络的定义认为如果两个节点拥有较多的共同邻接节点，则它们的相似度应该较大；反之，而若它们之间的共同邻接节点较少，则相似度较小。设节点vi的邻接节点的集合为Ni，节点vj的邻接节点的集合为Nj，则它们所拥有的共同邻接节点的集合可以表示为Ni∩ Nj。则这两个节点的相似度可以定义为：
但是由于在复杂网络中存在着“富人俱乐部”特性，即在复杂网络中的度分布呈现出长尾性质，度较小的节点占据网络中的大多数，而这些度较小的节点也倾向于网络中少量存在的度较大的节点，这些度较大的节点会因为不断的吸引导致度更大[7]。考虑到这些“富人节点”的度较大，使得其他节点和它们的共同邻接节点数量较多，导致它们的相似度很高，从而对其他非“富人节点”之间的相似度进行干扰。为了解决上述定义，相似度定义为：
在公式（3）中使用对数函数对复杂网络中的“富人节点”与其他节点进行相似度计算后相似度值要明显大于其他普通节点之间的相似度值的现象进行抑制。而由于当|Ni∩ Nj|<1时，相似度值为负的情况，公式（3）在对数函数内部进行加一，这样保证了相似度的值为正的完备性。
2.2 模块密度定义
Newman等人在文献[8]中提出了模块度Q作为网络社区划分质量的评价参数，其公式定义为：
在公式中， eii是边所连接的两个节点均在社区Gi内的边占网络中所有边的比例，ai是边所连接的节点中至少有一个在社区Gi内的边占网络中所有边的比例。模块度函数可以反映社区结构的明显程度，社区结构越明显，则模块度函数值越大，反之社区结构越弱，模块度函数值越小。
使用模块度作为社团划分的评价参数存在着对于小社团结构无法正确发现的分辨率极限问题，所以目前也有很多对于模块度进行改进的研究。Fortunato等人在文献[9]中提出了使用模块密度作为社区划分的评价函数，其定义为：
其中L（Vi， Vi）表示某个社团内部的连接数量，而
模块密度定义了所有子图平均内部连接率和所有子图与子图之间的平均外部连接率的差，反映了模块内部和模块之间的连接紧密程度。对于网络中的社团结构，其基础定义就是社团内部连接较为紧密而不同社团之间的连接较为稀疏。 2.3 算法描述
算法流程描述如下：
输入：无向网络图G=（V，E）
输出：网络G的社团结构
Step1：初始化网络社团结构，使得整个网络构成一个大型社团结构；
Step2：若网络中||V||=0或者||E||=0，则退出算法，否则计算每个节点对的相似度，并存于节点相似度矩阵中；
Step3：遍历节点相似度矩阵中的值，删除其中相似度最小的社團连接；
Step4：重复Step3直到社团连接数量小于阈值，形成一个终止的社团划分结果。
3 实验验证及分析
3.1 人工合成网络实验
为了验证算法的有效性，先使用Lancichinetti提出的基准网络对算法进行验证。Lancichinetti网络由128个节点组成，这些节点被划分为4个社团，每个社团包含32个节点，节点的平均度为16。该网络的构成可以通过混合参数γ进行调整，γ表示节点与该节点所属社区之外的所有社区之间的边数占该节点所有连接的百分数，所以γ越小则社团内部连接数较多，连接更为紧密，社区结构也就更加明显。随着混合参数的γ的增大，与其他社团的连接数量越多，社团结构也变得不明显，通常认为当γ=0.5时，社团结构已经较难进行识别。
实验根据Lancichinetti网络的规则，构造了γ取值范围为0到0.5的11个测试网络，对于每个测试网络运行算法20次，并记录社团划分结果。对于社团划分结果，使用标准互信息（Normalized Mutual Information）作为评价参数，标准互信息可以表示由算法发现的社区结构和真实社区结构之间的相似性，若两者完全一致，则标准互信息的值为1，反之，若完全不相似则为0。标准互信息公式定义为：
其中A代表真实网络的社团划分情况，CA表示真实网络中社团的数量，B表示算法得出的网络社团划分情况，CB表示由算法的得到的社团数量，Ci?表示邻接矩阵中第i行元素的和，C?j表示邻接矩阵中第j列元素的和。若使用算法得到的社团结构与真实网络的社团结构完全一致，则NMI（A，B）=1；反之若完全不一致则NMI（A，B）=0。实验结果如图1所示。
图1显示了γ取值不同时使用算法得出的NMI平均值的变化情况。随着混合参数γ的增加，NMI平均值逐渐减小，当γ=0.5时NMI平均值达到最小，而在γ≤0.35时NMI平均值均为1，即说明与真实网络的社团划分结果一致。从图1中可以看出，本文算法在混合参数γ增大的变化趋势中，相比于其他算法NMI平均值下降速度较慢，当γ≤0.35的情况下始终可以保持与真实社团结构一致。
3.2 真实网络数据实验
为了进一步验证算法的有效性，使用其他三个真实网络数据集来对算法进行评价：Zachery空手道俱乐部网络、美国大学橄榄球网络和球鼻海豚网络。Zachery空手道俱乐部网络是Zachery对一个空手道俱乐部观测得到的，网络中的节点代表俱乐部的成员，网络中的边数代表俱乐部成员之间的交流。网络的社区划分是分别由俱乐部管理者和俱乐部教练为核心的两个子网络。美国大学橄榄球网络表示美国大学橄榄球比赛2000年赛季第一分区的比赛日程安排表，网络中顶点表示球队，连接两个顶点的边表示这两个球队之间有比赛。这些球队被分为多个联盟，每一个球队平均和联盟内的球队进行了7场比赛，和联盟外的球队进行了4场比赛，因此具有较为明显的社区划分结构。球鼻海豚网络是由Lusseau通过7年时间观察生活在新西兰Doubtful Sound的62头海豚的行为编辑而成的社会网络，该网络之间的连接基于统计海豚之间有意义的频繁交往而建立起来的，62个节点根据交往的频繁程度被分为2组，即划分为2个社区。
对于每个真实网络，运行算法20次并保存社团划分结果，表1记录了每个真实网络的社团划分的社团数量和NMI平均值，图2-图4表示了社团划分结果的图形：
4 结论
本文针对复杂网络中的社团发现问题，基于节点的相似度构建了社团发现模型算法，通过使用人工合成网络进行实验并与其他算法进行对比，本文算法在社团结构不明显的情况下，仍然对社团结构具有一定的发现能力，证明了算法具有一定的优势。而通过真实网络数据的实验验证，证明了算法在真实的网络中的有效性。
参考文献：
[1] 刘大有，金弟，何东晓等.复杂网络中的社区结构算法综述[J].计算机研究与发展， 2013，50（10）： 2140-2154.
[2] Watts D J，Strogatz S H.Collective dynamics of ‘small-world’ networks[J].nature，1998， 393（6684）： 440-442.
[3] Girvanm，Newman M E J.Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America，2002，9 （12）：7821—7826.
[4] 张健沛，李泓波，杨静，等.基于拓扑势的网络社区结点重要度排序算法[J].哈尔滨工程大学学报，2012， 33（6）： 745-752.
[5] 程学旗，沈华伟.复杂网络的社区结构[J].复杂系统与复杂性科学，2011，8（1）： 57-70.
[6] 张健沛，李泓波，杨静.基于归属不确定性的变规模网络重叠社区识别[J].电子学报，2012， 40（12）： 2512.2518.
[7] 汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].清华大学出版社有限公司，2006.
[8] Newman M E J，Girvan M.Finding and evaluating community structure in networks[J]. Physical review E，2004，69（2）： 26-113.
[9] Fortunato S，Barthélemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences，2007，104（1）： 36-41.
[10] Lancichinetti，Andrea，Santo Fortunato，Filippo Radicchi.Benchmark graphs for testing community detection algorithms[J].Physical review E，2008（4）： 46-110.