一种复杂网络局部社区挖掘方法

摘要

本发明涉及网络技术领域，具体涉及到一种复杂网络局部社区挖掘方法，能够有效识别复杂网络的局部社区结构，具有较低的时间复杂度，误划分的节点数较少，包括如下步骤：以网络中的最大度节点为起始节点，计算其邻居节点，获得其邻居节点集；找到与最大度节点拥有最多共同邻居节点的节点；以此两个节点组成初始局部社区；获得初始局部社区的各邻居节点接近度，取接近度最大的节点加入初始局部社区形成新的初始局部社区；计算初始局部社区的Q值；重复上述步骤，直到形成新的初始局部社区Q值大于0或网络中节点为空。

主权项

复杂网络局部社区挖掘方法，其特征在于：包括如下步骤：1)以网络中的最大度节点为起始节点，计算其邻居节点，获得其邻居节点集；所述网络以G＝(V，E)表示，其中，V表示网络节点的集合，E表示网络连接的集合，找到V中度最大的节点v_a，计算其邻居节点集N(v_a)，N(v_a)＝{j|节点j与节点v_a直接相连}，并令V＝V‑v_a；2)找到与最大度节点拥有最多共同邻居节点的节点；3)将步骤1)获得的起始节点与步骤2)获得的与最大度节点拥有最多共同邻居节点的节点组成初始局部社区；4)获得初始局部社区的邻居节点的接近度，取网络中接近度最大的邻居节点加入初始局部社区形成新的初始局部社区，若接近度最大的邻居节点不止一个，则将这些接近度最大的邻居节点同时加入初始局部社区形成新的初始局部社区；具体包括如下步骤：41)利用下式，获得初始局部社区C在网络中的邻居节点集N(C)：$N\left(C\right)={\cup }_{i=1}^{\left|C\right|}N\left(i\right)-{\cup }_{i=1}^{\left|C\right|}i;$42)利用下式，计算N(C)中每一节点的接近度：$F(i,C)=\frac{K_i^{\mathrm{in}}}{K_i\underset{i\in N\left(C\right),j\in C}{\Sigma }{d}_{\mathrm{ij}}};$其中i∈N(C)，K_i表示节点i的度数，表示节点i与社区C内部节点的连接数，d_ij表示节点i与节点j之间的最短路径；43)加入接近度最大的节点v_x到初始局部社区C，C＝C+v_x，V＝V‑v_x；5)利用下式，计算步骤4)的初始局部社区C的Q值Q(C)：$Q\left(C\right)=\frac{E^{\mathrm{in}}\left(C\right)}{E^{\mathrm{in}}\left(C\right)+E^{\mathrm{out}}\left(C\right)}-\frac{E^{\mathrm{in}}(C-\{i\left\}\right)}{E^{\mathrm{in}}(C-\{i\left\}\right)+E^{\mathrm{out}}(C-\{i\left\}\right)};$其中i为最后加入社区C的节点或节点集，E^out(C)为社区C与社区C外部的连接数，Eⁱⁿ(C)为社区C内部的边数；当|C|为2时，令Q(C)＝1；6)重复步骤4‑5)，直到形成新的初始局部社区Q值大于0或网络中节点为空。