基于振荡器相位同步的符号网络社区检测方法

摘要

本发明提出了一种基于振荡器相位同步的符号网络社区检测方法，克服了现有技术中不适合于符号网络社区检测，且检测效率低，复杂性较高的缺陷。其实现步骤是：(1)生成邻接矩阵；(2)节点相位初始化；(3)更新节点相位；(4)判断更新后节点的相位是否稳定；(5)统计各个子区间节点的个数；(6)检测出符号网络的社区和重叠节点；(7)输出检测结果。本发明提出的方法使用改进后的振荡器模型，基于振荡器相位同步原理，能对符号网络实现社区检测，并通过微分方程的并行处理方式有效地提高了节点相位同步的效率，降低了符号网络社区检测的复杂性，可以有效地检测出符号网络的社区结构和重叠节点。

权利要求

1.一种基于振荡器相位同步的符号网络社区检测方法，具体步骤如下：(1)生成邻接矩阵：

将待检测符号网络中节点按照1～N依次编号，N表示该符号网络中节点的总个数；将待检测符号网络中节点i与节点j之间有正向连接边所对应的邻接矩阵中的元素aij设定为1；

将待检测符号网络中节点i与节点j之间无连接边所对应的邻接矩阵中的元素aij设定为0；

将待检测符号网络中节点i与节点j之间有负向连接边所对应的邻接矩阵中的元素aij设定为-1；获得与待检测符号网络所对应的邻接矩阵；

(2)节点相位初始化：

在[0,2π]相位值范围内，随机产生服从均匀分布的N个随机数，将所产生的随机数一一对应地设为符号网络中N个节点的初始相位；

(3)更新节点相位：

3a)将振荡器模型中的N个振荡器按照1～N依次编号，振荡器模型中的第i个振荡器对应被检测的符号网络中的第i个节点，第i个振荡器的相位更新值对应被检测符号网络中第i个节点的相位更新值；

3b)将节点的初始相位值代入以下振荡器模型，通过各个振荡器之间的相互正负耦合作用，求解微分方程，并行计算所有振荡器更新后的相位值集合P1；

其中， 表示第i个振荡器的相位随时间的变化，t表示振荡器相位更新一次的时间；

ωi表示第i个振荡器的固有频率，该固有频率在[-0.01,0.01]之间随机产生且服从均匀分布；Kp表示节点间的正耦合强度，Kn表示节点间的负耦合强度；N表示被检测符号网络中节点的总个数；|aij|表示对邻接矩阵中元素aij取绝对值操作；D表示振荡器j和振荡器i的相位差，D＝θj-θi,θi，θj分别表示第i个振荡器的相位值和第j个振荡器的相位值，i与j的取值范围为1～N；

3c)将所有振荡器相位的更新值集合P1代入振荡器模型中，得到所有振荡器再次更新后的相位值集合P2；将得到的所有振荡器再次更新的相位值集合P2继续代入振荡器模型中，得到所有振荡器下一次更新后的相位值集合P3，如此迭代更新，直到振荡器模型的运行时间T结束，得到所有振荡器n次更新的相位值集合Pn，Pn中的各个振荡器相位更新值对应被检测符号网络中各个节点相位更新值；

(4)判断更新后节点的相位是否稳定：

将每个节点更新前后的相位值相减再取绝对值，在所有绝对值中选取其中最大的一个绝对值，判断该绝对值是否小于阈值ε，若小于，则认为更新后所有节点的相位达到稳定，各社区内部节点达到同步状态，执行步骤(5)；否则，增大正耦合强度Kp，减小负耦合强度Kn，延长振荡器模型运行时间T，执行步骤(3)；

(5)统计各个子区间节点个数：

5a)将节点相位值的范围[0,2π]均匀地划分成多个长度为len的子区间；

5b)统计处于各个子区间范围内节点相位值个数，将节点相位值的个数作为节点的个数；

(6)检测出符号网络的社区和重叠节点：

6a)将子区间内节点个数大于0的相邻子区间划分为一组；

6b)在相邻子区间划分的组内的所有子区间中，搜索子区间节点个数的最大值；

6c)判断子区间节点个数的最大值是否大于等于阈值M，若大于等于，则将该组内所有子区间对应的节点作为符号网络的一个社区；若小于，则该组内所有节点为符号网络的重叠节点；

6d)对所有相邻子区间所划分成的组分别判断其节点个数的最大值与阈值M的大小关系，由此获得被检测符号网络的所有社区与重叠节点；

(7)输出检测结果：

将被检测符号网络的所有社区与重叠节点分别输出。

2.根据权利要求1所述的基于振荡器相位同步的符号网络社区检测方法，其特征在于，步骤(1)所述符号网络中节点的总个数为5～1200个。

3.根据权利要求1所述的基于振荡器相位同步的符号网络社区检测方法，其特征在于，步骤3b)所述的振荡器模型中的正耦合强度Kp为一个大于0的数值，负耦合耦合强度Kn为一个小于0的数值。

4.根据权利要求1所述的基于振荡器相位同步的符号网络社区检测方法，其特征在于，步骤3b)所述的振荡器相位更新一次的时间t＝0.05s，每隔0.05秒，每个振荡器的相位值更新一次；步骤3c)所述的振荡器模型的运行时间T的取值范围为2s≤T≤150s，振荡器运行结束时，振荡器相位更新的次数

5.根据权利要求1所述的基于振荡器相位同步的符号网络社区检测方法，其特征在于，步骤3c)在振荡器相位值更新过程中，对于超出[0,2π]区间的相位值都与2π取模，使所有振荡器的相位值都处在[0,2π]区间内。

6.根据权利要求1所述的基于振荡器相位同步的符号网络社区检测方法，其特征在于，步骤(4)所述阈值ε的取值范围为0<ε≤0.001。

7.根据权利要求1所述的基于振荡器相位同步的符号网络社区检测方法，其特征在于，步骤(5)所述每个子区间的长度len的取值范围为0.1≤len≤0.3。

8.根据权利要求1所述的基于振荡器相位同步的符号网络社区检测方法，其特征在于，步骤6c)与步骤6d)所述阈值M的取值范围为1≤M≤5，M为正整数。

说明书

基于振荡器相位同步的符号网络社区检测方法

技术领域

[0001] 本发明属于网络技术领域，更进一步涉及数据挖掘技术领域中的一种基于振荡器相位同步的符号网络社区检测方法。本发明通过引入改进的振荡器模型，利用振荡器相位同步原理，提高了并行处理能力，可快速有效地检测出符号网络的各个社区。

背景技术

[0002] 目前复杂网络已成为最前沿和最具挑战性的多学科性研究领域之一，现有复杂网络分析往往采用单一正关系边值模型来表示节点间的关系，然而现实社会网络关系中对于一个事物的评价或者人与人之间的关系，往往存在两面性，支持与反对，朋友和敌人，积极与消极，从无符号网络角度已经无法很好的解释这种网络结构关系。例如，在虚拟网络社区中，用户之间不仅存在朋友关系，也可能存在由黑名单产生的敌对关系。

[0003] 为了更加全面客观地发现社会网络数据的潜在特征关系，有必要对现有网络分析模型加以扩展得出符号网络分析模型。符号网络是指包含正负两种关系的复杂网络。例如在社会网络中，“喜欢”、“尊重”和“表扬”属于正向关系，而“厌恶”、“轻视”和“责备”属于负向关系。类似的正负关系在生物网络和科技网络等其它复杂网络中也广泛存在。符号网络中的社区是指多个不相交的节点集合，集合内的正关系稠密而集合间负关系稠密。符号网络社区结构挖掘方法的研究对分析复杂网络的拓扑结构和发现复杂网络中的隐藏规律具有十分重要的意义，例如识别社会网中的恐怖组织，预测蛋白质的未知功能，万维网的网页自动分类等。

[0004] 方平申请的专利“一种复杂网络局部社区发现方法”（专利申请号201210306231.5，公开号CN102819611A）中公开一种复杂网络的社区检测方法。该方法是以网络中的最大度节点为起始节点，计算其邻居节点，获得其邻居节点集；找到与最大度节点拥有最多共同邻居节点的节点；以此两个节点组成初始局部社区；获得初始局部社区的各邻居节点接近度，取接近度最大的节点加入初始局部社区形成新的初始局部社区；计算初始局部社区的Q值；重复上述步骤，直到形成新的初始局部社区Q值大于0或网络中节点为空。该方法存在不足之处是：该方法不适合于对存在负向关系的符号网络的社区检测。对于给定的网络，每次合并初始社区模块都必须查找初始社区邻居节点的接近度，然后计算合并初始社区模块所得的社区模块Q值，该专利计算过程过于复杂，需要较长的时间来计算节点的接近度，循环次数过多，降低了检测效率，耗费时间长。

发明内容

[0005] 本发明的目的在于上述克服现有技术的不足，提出一种基于振荡器相位同步的符号网络社区检测方法，以实现符号网络中社区结构的快速有效地进行检测。本发明使用改进的Kuramoto模型，基于振荡器相位同步原理，通过微分方程的并行处理方式使节点相位快速进行更新并达到同步，根据各个节点稳定时的相位，可快速有效地检测出符号网络的各个社区和社区间的重叠节点。

[0006] 实现本发明目的的具体步骤如下：

[0007] (1)生成邻接矩阵：

[0008] 将待检测符号网络中节点按照1～N依次编号，N表示该符号网络中节点的总个数；将待检测符号网络中节点i与节点j之间有正向连接边所对应的邻接矩阵中的元素aij设定为1；将待检测符号网络中节点i与节点j之间无连接边所对应的邻接矩阵中的元素aij设定为0；将待检测符号网络中节点i与节点j之间有负向连接边所对应的邻接矩阵中的元素aij设定为-1；获得与待检测符号网络所对应的邻接矩阵；

[0009] (2)节点相位初始化：

[0010] 在[0,2π]相位值范围内，随机产生且服从均匀分布的N个随机数，将所产生的随机数一一对应地设为符号网络中N个节点的初始相位；

[0011] (3)更新节点相位：

[0012] 3a)将振荡器模型中的N个振荡器按照1～N依次编号，振荡器模型中的第i个振荡器对应被检测的符号网络中的第i个节点，第i个振荡器的相位更新值对应被检测符号网络中第i个节点的相位更新值；

[0013] 3b)将节点的初始相位值代入以下振荡器模型，通过各个振荡器之间的相互正负耦合作用，求解微分方程，并行计算所有振荡器更新后的相位值集合P1；

[0014]

[0015] 其中， 表示第i个振荡器的相位随时间的变化，t表示振荡器相位更新一次的时间；ωi表示第i个振荡器的固有频率，该固有频率在[-0.01,0.01]之间随机产生且服从均匀分布；Kp表示节点间的正耦合强度，Kn表示节点间的负耦合强度；N表示被检测符号网络中节点的总个数；|aij|表示对邻接矩阵中元素aij取绝对值操作；D表示振荡器j和振荡器i的相位差，D=θj-θi,θi，θj分别表示第i个振荡器的相位值和第j个振荡器的相位值，i与j的取值范围为1～N；

[0016] 3c)将所有振荡器相位的更新值集合P1代入振荡器模型中，得到所有振荡器再次更新后的相位值集合P2；将得到的所有振荡器再次更新的相位值集合P2继续代入振荡器模型中，得到所有振荡器下一次更新后的相位值集合P3，如此迭代更新，直到振荡器模型的运行时间T结束，得到所有振荡器n次更新的相位值集合Pn，Pn中的各个振荡器相位更新值对应被检测符号网络中各个节点相位更新值；

[0017] (4)判断更新后节点的相位是否稳定：

[0018] 将每个节点更新前后的相位值相减再取绝对值，在所有绝对值中选取其中最大的一个绝对值，判断该绝对值是否小于阈值ε，若小于，则认为更新后所有节点的相位达到稳定，各社区内部节点达到同步状态，执行步骤(5)；否则，增大正耦合强度Kp，减小负耦合强度Kn，延长振荡器模型运行时间T，执行步骤(3)；

[0019] (5)统计各个子区间节点个数：

[0020] 5a)将节点相位值的范围[0,2π]均匀地划分成多个长度为len的子区间；

[0021] 5b)统计处于各个子区间范围内节点相位值个数，将节点相位值的个数作为节点的个数；

[0022] (6)检测出符号网络的社区和重叠节点：

[0023] 6a）将子区间内节点个数大于0的相邻子区间划分为一组；

[0024] 6b）在相邻子区间划分的组内的所有子区间中，搜索子区间节点个数的最大值；

[0025] 6c）判断子区间节点个数的最大值是否大于等于阈值M，若大于等于，则将该组内所有子区间对应的节点作为符号网络的一个社区；若小于，则该组内所有节点为符号网络的重叠节点；

[0026] 6d）对所有相邻子区间所划分成的组分别判断其节点个数的最大值与阈值M的大小关系，由此获得被检测符号网络的所有社区与重叠节点；

[0027] (7)输出检测结果：

[0028] 将被检测符号网络的所有社区与重叠节点分别输出。

[0029] 本发明与现有技术相比存在以下优点：

[0030] 第一，由于本发明使用了改进的振荡器模型，引入了负耦合强度，根据符号网络社区内部节点正向连接稠密，邻接矩阵中对应元素多数为1，作用的正耦合强度较多，优先使社区内部的节点的相位趋于同步；而不同社区之间节点负向连接稠密，邻接矩阵中对应元素多数为-1，作用的负耦合强度较多，从而将不同社区的节点对的相位分离开。这样就使得符号网络中同一个社区内的节点的相位聚集，形成一个同步组，而不同社区间的节点的相位分离，同时重叠节点的相位介于两个不同社区节点的相位之间，克服了现有技术复杂网络社区检测技术不适合于符号网络社区检测的缺陷，使得本发明大大的提高了符号网络的社区检测效果。

[0031] 第二，由于本发明利用了振荡器的相位同步原理，更新节点的相位是一个迭代的过程，提高了并行处理能力，加快了相位求解过程，克服了现有技术的计算时间长，效率低，复杂度较高的问题，使得本发明可大大降低符号网络社区检测的复杂性，提高检测效率。

附图说明

[0032] 图1为本发明的流程图；

[0033] 图2为本发明使用的构造符号网络的拓扑图；

[0034] 图3为本发明对构造符号网络的仿真结果示意图；

[0035] 图4为本发明使用的Gahuku-Gama符号网络的拓扑图；

[0036] 图5为本发明对Gahuku-Gama符号网络的仿真结果示意图。

具体实施方式

[0037] 下面结合图对本发明做进一步的详细描述。

[0038] 参照附图1，本发明的步骤如下：

[0039] 步骤1.生成邻接矩阵。

[0040] 将待检测符号网络中节点按照1～N依次编号，N表示该符号网络中节点的总个数；将待检测符号网络中节点i与节点j之间有正向连接边所对应的邻接矩阵中的元素aij设定为1；将待检测符号网络中节点i与节点j之间无连接边所对应的邻接矩阵中的元素aij设定为0；将待检测符号网络中节点i与节点j之间有负向连接边所对应的邻接矩阵中的元素aij设定为-1；获得与待检测符号网络所对应的邻接矩阵。N的取值范围为5～1200。

[0041] 参照附图2，在图2中，待检测符号网络采用一个简单的构造符号网络，该网络由14个节点组成，N=14，图中实线代表节点之间的正向关系，虚线代表节点之间的负向关系。

[0042] 步骤2.节点相位初始化。

[0043] 在[0,2π]相位值范围内，随机产生且服从均匀分布的N个随机数，将所产生的随机数与符号网络中节点的初始相位一一对应。

[0044] 本发明的实施例中，网络节点数为14，在相位值[0,2π]范围内随机产生14个随机数[5.0279，2.7107，5.7218……3.9085，2.2051]，将每个随机数作为每个节点的初始相位，即将5.0279作为第一个节点的初始相位，将2.7107作为第二个节点初始相位，依次类推。

[0045] 步骤3.更新节点的相位。

[0046] 将振荡器模型中的N个振荡器按照1～N依次编号，振荡器模型中的第i个振荡器对应被检测的符号网络中的第i个节点，第i个振荡器的相位更新值对应被检测符号网络中第i个节点的相位更新值。

[0047] 将节点的初始相位值代入以下振荡器模型，通过各个振荡器之间的相互正负耦合作用，求解微分方程，并行计算所有振荡器更新后的相位值集合P1。

[0048]

[0049] 其中， 表示第i个振荡器的相位随时间的变化率，t表示振荡器的运行时间间隔;ωi表示第i个振荡器的固有频率，Kp表示节点间的正耦合强度，是一个大于0的数值，当任意两个节点i与节点j有正向连接时，即aij=1时，节点的相位为正耦合，此时振荡器模型中只有第一个分式对符号网络中节点相位起作用，即只有正耦合强度起作用；Kn表示节点间的负耦合强度，是一个小于0的数值，当任意两个节点i与节点j有负向连接时，即aij=-1时，节点的相位为负耦合，此时振荡器模型中只有第二个分式对符号网络中节点相位起作用，即只有负耦合强度起作用；当任意两个节点i与节点j无连接时，即aij=0，此时振荡器不对网络节点的相位发生作用；N表示被检测符号网络中节点的总个数；|aij|表示邻接矩阵中元素aij的绝对值；sin(D)=sin(θj-θi)表示对振荡器j和振荡器i的相位差取正弦函数，θi，θj分别表示第i个振荡器的相位值和第j个振荡器的相位值，i与j取值范围为1～N；

[0050] 将所有振荡器相位的更新值集合P1代入振荡器模型中，得到所有振荡器再次更新后的相位值集合P2；将得到的所有振荡器再次更新的相位值集合P2继续代入振荡器模型中，得到所有振荡器下一次更新后的相位值集合P3，如此迭代更新，直到振荡器模型的运行时间T结束，得到所有振荡器n次更新的相位值集合Pn，Pn中的各个振荡器相位更新值对应被检测符号网络中各个节点相位更新值。

[0051] 振荡器模型的运行时间为T，T的取值范围1≤T≤150，时间间隔为0.05，每隔0.05秒，每个振荡器的相位值更新一次。在振荡器相位值更新过程中，对于超出[0,2π]区间的相位值都与2π取模，使所有振荡器的相位值都处在[0,2π]区间内。

[0052] 在本发明实施例中，符号网络结构图中的每个节点与一个振荡器一一对应，分别编号为1到14；振荡器的相位变化值对应节点的相位变化值，在Matlab环境下，设正耦合强度Kp=2，负耦合强度Kn=-15，振荡器模型的运行时间T为80秒，间隔为0.05，通过求解振荡器微分方程，不断迭代更新网络中各个节点的相位值。

[0053] 参照附图3，图3（a）为振荡器相位变化图，图3（a）中的14条线分别代表了编号为1～14的振荡器相位值随时间不断变化更新的过程，振荡器运行结束时，更新的相位值集合Pn为[1.68727，1.68729，1.68725......2.9887，3.2959]。

[0054] 步骤4.判断节点的相位是否稳定。

[0055] 将每个节点更新前后的相位值相减再取绝对值，在所有绝对值中选取其中最大的一个绝对值，判断该绝对值是否小于阈值ε，若小于，则认为更新后所有节点的相位达到稳定，各社区内部节点达到同步状态，执行步骤(5)；否则，增大正耦合强度Kp，减小负耦合强度Kn，延长振荡器模型运行时间T，执行步骤(3)。

[0056] 在本发明的实施例中，当振荡器运行16秒，节点的相位更新320次时，符号网络内所有节点更新后的相位值与更新前的相位值的差值最大值小于0.001，所有节点的相位达到稳定，符号网络社区内部节点达到同步状态。

[0057] 步骤5.统计各个子区间节点的个数。

[0058] 将节点相位值的范围[0,2π]均匀地划分成多个长度为len的子区间；每个子区间的长度len的取值范围为0.1≤len≤0.3。统计处于各个子区间范围内节点相位值个数，将节点相位值的个数作为节点的个数。

[0059] 在本发明的实施例中，当所有节点的相位稳定时，将[0,2π]相位值均匀划分为40个子区间，子区间的长度 子区间分别表示为S1,S2，……，S39，S40，统计的每个子区间内节点的相位处于该子区间范围内节点的个数如下表所示：

[0060]S1 S2 S3 S4 S5 S6 S7 S8 S9 S10
0 0 0 0 0 0 0 0 0 0
S11 S12 S13 S14 S15 S16 S17 S18 S19 S20
6 0 0 0 0 0 0 0 1 0
S21 S22 S23 S24 S25 S26 S27 S28 S29 S30
2 0 1 0 0 0 0 0 0 0
S31 S32 S33 S34 S35 S36 S37 S38 S39 S40
4 0 0 0 0 0 0 0 0 0

[0061] 步骤6.检测出符号网络的社区和重叠节点。

[0062] 将子区间内节点个数大于0的相邻子区间划分为一组。

[0063] 在相邻子区间划分的组内的所有子区间中，搜索子区间节点个数的最大值。

[0064] 判断子区间节点个数的最大值是否大于等于阈值M，若大于等于，则将该组内所有子区间对应的节点作为符号网络的一个社区；若小于，则该组内所有节点为符号网络的重叠节点。

[0065] 对所有相邻子区间所划分成的组分别判断其节点个数的最大值与阈值M的大小关系，由此获得被检测符号网络的所有社区与重叠节点。

[0066] 在本发明的实施例中，子区间内节点个数大于0的相邻的子区间划分后的组为：A:{S11}，B:{S31}，C:{S19}，D:{S21}，E:{S23}。

[0067] 参照图3（b），图3（b）为振荡器相位稳定时相位值的分布图。图3（b）中的星星的高度数代表了处在各个子区间内节点的个数。设阈值M=3，A组内子区间节点个数的最大值为6，该组对应的节点{1,2,3,4,5,6}即确定为符号网络的一个社区，B组、D组、内子区间节点个数的最大值为1。根据判定准则，这两组对应的节点{13}，{12}确定为符号网络的重叠节点，C组内子区间节点个数的最大值为2，小于阈值M，该组对应的节点{11},{14}确定为符号网络的重叠节点，E组内子区间节点个数的最大值为4，大于阈值M，所以该组对应的节点{7,
8,9,10}确定为符号网络的另一个社区。

[0068] 步骤7输出检测结果。

[0069] 将被检测符号网络的所有社区与重叠节点分别输出。

[0070] 参照图3（b），在本发明的实施例中，被检测符号网络的社区有2个，分别是节点{1,2,3,4,5,6}，节点{7,8,9,10}。重叠节点有4个，分别是{11}，{12}，{13}，{14}。

[0071] 通过以上结果，实现了对待检测符号网络的社区检测，获得了符号网络的各个社区和重叠节点。

[0072] 下面结合仿真图对本发明的效果做进一步的描述。

[0073] 1.仿真条件：

[0074] 本发明是在CPU为core22.4GHZ、内存2G、WINDOWS XP系统上使用Matlab2011b进行仿真的。

[0075] 2.仿真内容：

[0076] 选取图2所示网络和图4所示Gahuku-Gama符号网络作为仿真对象。图2网络由14个节点组成，节点之间的连接边代表成员之间的某种关系；Gahuku-Gama符号网络由16个节点组成，每个节点代表新几内亚16个不同的部落，节点之间的连接边代表这些部落之间的相互政治关系，可得到该网络对应的邻接矩阵。

[0077] 仿真中两个网络用到的参数如下表所示：

[0078]符号网络 Kp Kn ε len M
图2所示网络 2 -25 0.001 π/20 3
Gahuku-Gama符号网络 网20 -10 0.001 π/20 2

[0079] 参照附图2，在以上参数条件下对图2所示符号网络进行检测：图2中，圆形对应的节点{1，2,3,4,5,6}为符号网络的一个社区，方形对应的节点{7,8,9,10}为符号网络的一个社区，六边形对应的节点{11},{12},{13},{14}为网络的重叠节点。验证了本发明的有效性。

[0080] 参照附图4，在以上参数条件下对图4所示的Gahuku-Gama符号网络进行仿真：

[0081] 参照图5（a），图5（a）为振荡器相位变化图。当节点相位更新80次时，相位达到稳定，图中的16条线分别代表了编号为1～16的振荡器相位值随时间不断变化更新的过程。

[0082] 参照图5（b），图5（b）为振荡器相位稳定时相位值的分布图。取阈值M=2，3个相邻的子区间组内节点个数的最大值均大于M，所以它们为该符号网络的3个社区；在图5中，圆形对应的节点{3,4,6,7,8,11,12}为符号网络的一个社区；方形对应的节点{1,2,15,16}为符号网络的一个社区；六边形对应的节点{5,9,10,13,14}为符号网络的一个社区，本网络没有重叠节点。

[0083] 从以上说明可以看出，本发明可以快速准确地检测出符号网络的各个社区和重叠节点。