摘要：为了准确地检测出复杂网络的社团结构，提出一种基于信号自适应传递的社团发现方法。首先使信号在复杂网络上自适应地传递，从而获取网络中各节点对整个网络的影响向量，然后把网络中节点的拓扑结构转化成代数向量空间上的几何关系，最后结合聚类特性发现网络中的社团结构。为获取更加合理的空间向量，提出最佳传递次数，缩小搜索空间，增强算法寻优能力。该算法在计算机生成网络、Zachary网络和美国大学生足球赛网络上进行实验测试， 并与中文全称，无GirvanNewmanGN算法、谱聚类算法、极值优化算法和信号传递算法进行实验对比，社团划分的准确性和精确性均有所提高，证明该算法具有有效性和可行性。
关键词：复杂网络；社团结构；自适应；传递次数；社团发现算法
中图分类号： TP393.02 文献标志码：A
英文摘要
Abstract：In order to accurately detect the community structure of complex networks， a community detection algorithm based on signal adaptive transmission was proposed. First， the signal was adaptively passed on complex networks，thereby getting the vector affecting on the entire network of each node， then the topological structure of each node was translated into geometrical relationships of algebra vector space. Thus， according to the nature of the clustering， the community structure of the network was detected. In order to get the feasible spatial vectors， the optimum transfer number was determined， which reduced the searching space， and effectively strengthened the search capability of community detection.The proposed algorithm was tested on computergenerated network， Zachary network and American college football network. Compared with 英文全称GirvanNewman （GN） algorithm， spectral clustering algorithm，extremal optimization algorithm and signal transmission algorithm， the results show that the accuracy and precision of the proposed community spanision algorithm is feasible and effective.
英文关键词
Key words：complex network； community structure； adaptability； transfer number； community detection algorithm
0 引言
关于复杂网络的研究已成为当今科学界的前沿和热点，如今已遍及学术界的各个领域，如人际关系网、万维网、新陈代谢网等。人们通过大量的研究表明，复杂网络除了有小世界性、无标度性之外，社团结构也越来越被广泛关注。社团结构指的是整个网络由若干个子集组成，各子集之间的连接相对稀疏、而子集内部的连接相对稠密[1]。社团结构的发现对于人们深入地理解网络的动态性以及结构功能等十分重要。
近年来，复杂网络中社团结构的研究受到了很多学者的关注，许多社团发现算法 [2-3]被相继提出。算法大致分为三大类：启发式方法、基于优化的方法和基于相似性的方法。启发式方法主要是把复杂网络中的社团发现问题转变成预定义的启发式规则的设计问题，如GN（GirvanNewman）算法[4]、极值优化算法[5]、WuHuberman算法[6]等；基于优化的方法是将复杂网络聚类问题转化为优化问题，通过对目标函数的最优化预定义而得到复杂网络的社团结构，如谱聚类算法[7]、信号传递算法[8]等；基于相似性的方法是根据网络拓扑结构来定义节点间的相似度，如基于结构全等的相关系数 [9] 、节点聚类中心度 [10]等。现如今的社团发现算法如何能较好、较快地划分社团，即所有社团的发现算法中复杂度和查找的准确性依然是最需要解决的两个问题。
基于信号传递的社团发现算法在降低算法的复杂度和提高划分社团结构的准确率方面具有重要的意义，但是对于直径较大的网络，当信号仅传递3或4次时，边缘节点是无法获取信息的，因而导致社团划分的结果较差。针对上述问题，本文提出一种基于信号自适应传递的社团发现算法，在信号传递的过程中，传递次数不再是静态固定值，而是自适应的动态改变值，从而使所有节点都能够获取信息而又不会出现信息溢出，增强了算法优化的能力。
1 信号传递算法
Hu 等[8]提出了通过在复杂网络中进行传递信号来发现社团的方法。该方法的思想是将每个节点看作是一个可以受启发的系统，该系统能够发送、接收并记录信号。首先，随机在网络中选择一个节点作为信息源并给予初始的单位信息，而其他节点没有信息；然后信息源把信息平均传递给相邻节点和自己；随后，获得信息的节点再传给相邻节点和它自己，同时获取由其他节点发送的信息，经过传递3或4次后，大部分节点都获取一定量信息源的信息。因此，信号在节点上的传递可以看作是源节点对于整个网络的影响。对于有n个节点的网络，通过这个传递过程可以把网络节点的拓扑结构转化为n维几何空间向量的形式。图1说明了在5个节点构成的网络上的信号传输的过程。 以节点1这里的1指源节点为1个，还是为节点1。这里的1指节点1，改为节点1。节点1指圆圈旁边的数字，不是圆圈里的，已核实无误为源节点进行信号传输的模拟过程可以将上述的传递过程用公式Xs=（I+A）上标T是表示转置应为正，还是变量应为斜。这里的T是变量，所以改为斜体。公式中的T丢失了，麻烦公式中加上T。
T来表示，其中A是网络的邻接矩阵，I是单位矩阵，T是网络中传递信号的次数，Xs是网络中各节点对源节点的影响向量。
经过上述的信号传递过程，然后把网络的拓扑结构映射为向量，之后选取合适的相似度计算节点间的相似程度，最后运用聚类算法划分社团结构。
2 基于信号自适应传递的社团发现算法
2.1 传递次数自适应动态调整
信号传递过程中的传递次数T是影响网络空间向量的重要参数，它决定了划分社团结构效果的优越性。基于信号传递的社团发现算法中，传递次数T始终是静态固定值，无法动态地调整算法在不同网络中的信息传递性能。若T值过大，可能导致信息重复传递以至于其他节点所包含信息量过多而无法与源节点区分；若T值过小，边缘节点可能无法获取到源节点的信息。针对上述问题，本文提出自适应动态地调整传递次数的策略，使该算法在传递过程中不再是静态固定值，而是自适应的动态改变值，从而更好地提升算法在不同网络中的信息传递性能。
自适应动态调整传递次数的策略：当信号传递算法中传
递次数为T=i（i=0，1，…， n）时，遍历整个网络，看是否每个节点都有信息量，若还有节点没有信息量，则更新传递次数T；否则，停止信号传递，并将此时的传递次数定义为最佳的传递次数Tbest。这样，根据遍历的结果来动态更新本次迭代的传递次数，具有更好的自适应性。因此，实现传递次数的自适应动态调整，算法的寻优精度将会有较大的提高。为验证此结论的合理性，下面通过实验来证明。
不同传递次数T与准确度关系图中横坐标k是否应小写，与文中描述一致？应改为小写，而且图中的虚线需要改为实线，相关图标我已附件发送。
由图2可知，传递次数取Tbest时获取的社团准确度最高，就是说传递次数取Tbest时是可行且最佳的。
2.2 算法描述
在无向网络G中任意选择一个节点作为源节点S并赋予一个单位信息，而其他节点没有信息。其中，A为网络G的邻接矩阵；T为信号传递次数；XS表示节点节点S是应与Xs的下标一致小写，还是大写，请核实？S均为大写。下标也大写
S对网络的影响，即节点S映射到n维空间向量。算法具体步骤如下：
输入 网络的邻接矩阵A；
输出 网络的社团结构。
步骤1 初始化X0S=（0，0，…，1，…，0），T=0。
步骤5 结合社团的定义以及模块度、准确度获取最佳社团结构，并画出此时所获取的社团结构关系图。
上述算法中遍历的过程相当于对整个网络进行一次广度优先搜索，该搜索过程的时间复杂度为O（n2），因此在最坏的情况下此算法的时间复杂度为O（n2+n），一般情况下，算法的复杂度远远小于该复杂度。
3 实验与分析
在计算机生成网络和真实网络上分别进行了实验，测试结果证明了本文算法的有效性。
3.1 计算机生成网络
在获取社团结构之后，一般情况下并不知道这个社团结构能否反映网络的本质，并且不知道社团个数是否为最合适。所以还需要通过计算社团的准确度和精确度来确定社团划分的效果，准确度指运用某种算法获得网络的社团结构和网络实际社团结构的接近程度，而精确度指某种网络运用同样的算法划分社团结构若干次而获得的结果之间的差异性。
为了进一步验证本文算法的有效性和准确性，仍然选择2.1节中的计算机生成网络，分别与GN算法[4]、极值优化算法[5]、谱聚类算法[7]、信号传递算法[8]作比较，比较结果如图3所示。
不同算法准确度和精确度的变化情况是否应给出“准确度”和“精确度”含义？
图3是随着计算机生成网络中社团之间〈kout〉变化准确度和精确度的变化情况。从图3可知，本文算法准确度比GN算法、谱聚类算法要好，与极值优化算法信号传递算法相近，精确度与谱聚类算法、信号传递算法和GN算法类似，但比极值优化算法高很多。由上述可知，该算法具有较高的准确度和精确度。
3.2 真实网络
3.2.1 Zachary空手道俱乐部网络
其中夹角余弦为节点相似度量，并采用Ward凝聚聚类技术。
4 结语
本文基于自适应的思想对现有信号传递算法进行了改进，提出一种有效社团发现的算法。经实例验证，当信号传递次数根据网络的规模而自适应动态地调整时，获取的空间向量最佳，因为此时检测网络的社团效果比传统方法更为准确。本文算法克服了原有信号传递算法仅对小规模网络正确划分的缺陷，该算法对较大网络的划分同样具有较高准确度。但本文的研究仅限于不重叠的无权网络，对于加权重叠网络的研究将是下一步的研究方向。此外，信息孤岛问题也将是以后需要考虑的问题。
参考文献：
[2]SHI C， CAI Y N， FU D，et al. A link clustering based overlapping community detection algorithm [J]. Data & Knowledge Engineering， 2013， 87： 394-404.
[3]LI K， PANG Y. A unified community detection algorithm in complex network [J]. Neurocomputing， 2014， 130： 36-43.
[5]DUCH J， ARENAS. A community detection in complex networks using extremal optimization [J].Physical Review E， 2005， 72（2）： 027104.
[6]WU F， HUBERMAN B A. Finding communities in linear time： a physics approach [J]. The European Physical Journal B， 2004， 38（2）： 331-338.
[8]HU Y，LI M，ZHANG P， et al.Community detection by signaling on complex networks [J].Physcial Review E： Statistical， Nonlinear and Soft Matter Physics， 2008， 78： 016115.
