基于神经网络的社团检测算法*

代婷婷，韩 艳，虎亚楠

(昭通学院 数学与统计学院，云南 昭通 657000)

1 引言

在社团检测算法中历史悠久的、比较经典的有Kernighan-Lin算法和谱平分方法[1,2],其次就是Girvan和 Newman[3]在2002年提出的一种通过边移除按层次分解网络的社团结构方法(GN).在后一算法中提到了模块度，之后模块度很快成为了衡量社团检测结果的通用指标.随着研究的不断推进，2014年，Maria C.V. Nascimento[4]提出了一种基于聚类系数的谱启发式算法(SPEC)，该算法克服了启发式算法的规模缺陷，具有很好的性能.2017年，邓小龙等人[5]提出了基于矢量影响力聚类系数的高效有向网络社团检测算法.该算法从构成社团最基础的三角形极大团展开数学推导，并且提出一种有向社团结构划分目标函数，具有不错的精确性.2018年，郑少强等人[6]提出一种基于聚类系数的标签传播算法，对节点按度和聚类系数的大小影响力排序，根据影响力做初始划分，再进行标签传播.本文主要是依据Newman提出的模块度社团划分评价指标，提出了一种基于神经网络的社团划分方法，此方法可以找到最优的模块度函数值，对应地可以找到最优的与实际网络非常接近的划分.

2 理论与方法

2.1 连续神经网络(CNN)

考虑微分方程

(1)

其中，A是一个n×n的实对称矩阵，可以将其视为神经网络的连接权强度，X∈Rn，视为神经网络的状态.方程(1)描述了一类连续型的全反馈人工神经网络.文献[7]给出了一种电路模拟方法，当A为对称正定矩阵时，Oja等[8]根据神经网络的Hebbian规则，将方程(1)作为一种无教师指导的神经网络学习过程，研究了输入空间提取特征主元的问题，证明了方程(1)任意从初始值出发的解都收敛于A的最大特征值对应的特征向量.这点可以由下面的定理保证.

定理2[7]假设A的最大特征值λ>0，则式(2)的从任意初值X(0)出发的解均收敛于A的最大特征值λ对应的特征向量.

该定理给出了一种新的求解矩阵特征值和特征向量的方法.

本文将 Newman[9]的基于模块度函数Q的矩阵特征值和特征向量提取复杂网络中社团结构的算法和神经网络算法求解矩阵特征值特征向量的算法结合起来得到了一种新的基于连续神经网络的社团结构检测算法，简称CNN算法，模型为

(2)

其中,B为式(4)定义的复杂网络的模块度矩阵，X∈Rn.由定理2知，从任意初值出发，方程(2)的解都会收敛到模块度矩阵B的最大特征值对应的特征向量.结合Newman的特征值特征向量算法，我们就可以根据方程(2)的解中元素的符号将复杂网络中的社团结构提取出来.

2.2 离散Hopfield神经网络(DHNN)算法

离散的Hopfield神经网络是一个单层全连接网络，有n个神经元节点，每个神经元的输出均接到其它神经元的输入.各节点没有自反馈,每个节点都可处于一种可能的状态(1或-1)，即当该神经元所受的刺激超过其阈值时，神经元就处于兴奋状态(比如1)，否则神经元就始终处于抑制状态(比如-1).

对于以符号函数为激活函数的网络，网络的方程可写为

xi(t+1)=sgn[ui(t)]，i=1,2,…,n，

(3)

其中W为连接权矩阵，θ为阈值向量.将以上Hopfield网络简记为H=(W,θ).

为了避免求具体解，而只利用符号解决复杂网络的分类问题，本文提出了另一种新的复杂网络社团结构提取算法—离散Hopfield神经网络提取社团结构算法，简称为DHNN算法.

根据离散Hopfield神经网络的形式，可以将连续神经网络(2)离散化构造离散Hopfield神经网络模型，最后根据提出的离散Hopfield神经网络模型达到稳定状态时稳定点中元素的符号将复杂网络的节点分为两类.

将式(2)连续的微分方程写成差分的形式，可以得到

所以

x(t+1)=Bx(t)+x(t)-xT(t)Bx(t)x(t).

(4)

将式(2)与式(4)结合，就可以得到离散的神经网络模型

x(t+1)=sign(Bx(t)+x(t)-xT(t)Bx(t)x(t)).

(5)

对于离散的Hopfield神经网络H=(W,θ),取

θ=x(t)-xT(t)Bx(t)x(t)=0,

则网络模型可以变形为

x(t+1)=sign(Bx(t)).

(6)

将式(6)中的模块度矩阵B拆开就可以得到

(7)

其中，An×n表示复杂网络的邻接矩阵，X(t)表示一个取值±1的n维列向量，ki表示节点i的度，符号函数为

3 实证分析

本文用8个文献中广为引用的数据库对本文所提出的两个社团结构提取算法进行验证，验证结果表明，所提出的算法从准则函数上看均优于其它方法.

3.1 实验数据

(1) 空手道俱乐部网络(Zachary’s Karate Club)[10]在社团提取问题中是被应用最为广泛的例子之一.空手道俱乐部网络由34个节点组成，每个节点表示一个成员，网络中的78条边表示成员之间的社会交往关系.由于俱乐部主管和校长之间发生矛盾，俱乐部成员就被分成了分别以主管和校长为中心的两个社团.此网络如图1所示.

图1 空手道俱乐部网络

(2) 其它实际网络：Lusseau提出了海豚关系网，由62个节点159条边组成.Internet含有22 963个节点，Netscience _ coauthor 含有1 589个节点，Polbooks 含有105个节点，Power_grid含有4 941个节点，football含有115个节点，Celegans含有297个节点.这些网络的数据可在下面的网址下载到：http://www-personal.umich.edu/～mejn/netdata/.

3.2 实验结果分析

3.2.1空手道俱乐部网络(Zachary’s Karate Club)实验结果分析

在实验部分，我们将在俱乐部网络上分析连续型神经网络算法、离散型Hopfield神经网络算法的分类效果.首先用特征值和特征向量算法、连续神经网络算法、离散Hopfield神经网络提取空手道俱乐部网络中的社团结构，结果如表1、表2所示.

表1 连续算法提取的空手道俱乐部网络中社团结构的分类结果

表2 离散算法提取的空手道俱乐部网络中社团结构的分类结果

表1、表2列出了特征向量算法、连续算法和离散Hopfield神经网络算法在空手道俱乐部网络上的仿真结果.从实验结果发现，特征向量算法、连续算法对空手道俱乐部网络的分类的结果相同，而离散Hopfield神经网络算法对空手道俱乐部网络的分类结果与前两种算法却不相同.它将9这个节点分到了+1所表示的类中，对应的模块度函数的值Q=0.371 8比特征向量算法、连续算法得到的模块度函数值Q=0.371 5大，这里我们是用+1，-1来区别的.在以模块度函数值Q的大小作为社团划分优劣的指标时，显然用离散Hopfield神经网络算法提取的社团结构更优.三种方法的分类结果在实际网络上的表现如图1、图2所示.

图2 DHNN算法对空手道俱乐部网络的分类结果

采用离散Hopfield神经网络算法提取空手道俱乐部网络中的社团结构时，对于任意给定的初值，网络(6)经过若干次迭代后网络最终收敛到一个长度为2的极限环，并且对应于一个合理的社团结构(community)，得到的目标值Q=0.371 8(用+1，-1来区别)，就是将图1中浅(黄)色9改为深(紫)色9后得到图2的结果对应的目标值，而我们用特征值特征向量的算法和连续算法得到的模块度函数值为Q=0.371 5(采用+1，-1来区别)，即用本文所设计的Hopfield神经网络得到的目标值大于特征向量法、连续算法得到的目标值.得到这个结果不是偶然的，而是本文的离散Hopfield神经网络造成的，因为无论运行多少次，网络划分的结果都与特征值算法的结果相差一个顶点，而且特征值特征向量算法得到的结果并不是本文所设计的离散Hopfield神经网络的稳定点，要去掉9这个点后才是网络的稳定点而且目标值才最优.由此可以看出，本文所提出的离散型Hopfield神经网络算法在提取复杂网络中的社团结构时，不需要计算模块度矩阵B的最大特征值对应的特征向量，这显然为此算法的一个优势.

3.2.2其它实际复杂网络上的实验结果及分析

前面我们用本文提出的算法在空手道俱乐部网络(Zachary’s Karate Club)上进行了实验，并且对实验结果进行了分析，为了进一步证实本文算法的有效性，我们将用本文的算法在Internet、Netscience _ coauthor、Polbooks、Power_grid、football和Celegans六个网络上进行实验.由于这六个网络的规模大，含有的节点数目很多，所以没有将实验分类的结果一一列出，只是在表5中给出了特征值特征向量算法、连续算法和离散算法在8种不同实际网络上仿真得到的Q值.其中对有些网络用传统的特征值算法计算已经无法在个人电脑中进行了，但本文所提出的DHNN算法仍能够在较短时间内完成.

表3 8种复杂网络在连续算法和离散算法下的模块度函数Q值的比较

观察表3，我们发现离散算法与特征向量算法、连续算法相比有两个优势：首先，在复杂网络的节点较多的时候，离散算法可以在家庭用的笔记本电脑上算出复杂网络的模块度函数的Q值，而特征向量算法却不能；其次，用离散算法在每个复杂网络上得到的模块度函数Q值均大于用特征向量算法、连续算法得到的Q值，这说明本文提出的离散算法在提取复杂网络中的社团结构时，算法性能较其它两种方法更好.

4 结论与展望

本文提出的两种算法都是将模块度函数Q的值作为评价社团划分优劣的指标，根据复杂网络的模块度矩阵的最大特征值对应的特征向量里面元素的符号将复杂网络的节点分为两类.在连续型神经网络方法中，我们通过一个微分方程系统计算出了复杂网络模块度矩阵的最大特征值对应的特征向量，与Newman的特征值特征向量算法相比计算量较小，而且所对应的Q值也较优.本文提出的算法尚有许多不足之处，比如对某些规模庞大的网络，划分的次数比较多，算法的复杂度较高，若能降低运算次数则此方法会更好；另外，此算法的评价指标比较单一，若再加入一个评价指标，社团结构的划分可能会更合理.在下一步工作中，考虑针对以上的问题将本文的方法作改进和优化.