基于分形特征的复杂网络社区发现方法

摘要

基于分形特征的复杂网络社区发现方法，包括离线的静态复杂网络的社区发现的处理和在线动态复杂网络的社区发现的处理两个阶段。本发明充分利用复杂网络的多尺度特征，用重正化过程作为联系不同尺度间的桥梁，从而达到将之前的社区结构信息为新的社区结构发现所用的目的，实现了增量式的社区发现，为研究动态复杂网络的社区结构做了新的尝试，并得到了比较满意的结果。

主权项

基于分形特征的复杂网络社区发现方法，其特征在于：包括离线的静态复杂网络的社区发现的处理和在线动态复杂网络的社区发现的处理两个阶段，其中，第一阶段离线的静态复杂网络的社区发现的处理，其过程如下：步骤1、输入复杂网络的拓扑结构G＝(V,E)；复杂网络用无向图G＝(V,E)来表示，V和E分别为结点和边的集合；步骤2、初始化，具体为，计算V中每个结点的度，结点n_i的度记为deg_i，表示网络中连接到结点的边的个数；对E中的每条边设定权值w_ij，若n_i和n_j有一个度为1，则令其权值为0，其它情况权值为1；令重正化次数k＝0，并令d＝0，d_k＝0，C(d)_k＝0，其中，d是社区两节点间最小距离，第一次d＝0，d_k是为社区两节点的叠加距离，d_k＝0指在k＝0的情况下，d_k赋给0值，C(d)_k是社区两节点的关联函数，在k＝0次的情况下C(d)_k赋给0值；步骤3、计算相邻结点的距离，重正化距离最小的结点，具体为：若复杂网络中所有的原始点都已经被重正化过，则跳至步骤4更新网络，否则继续此步骤；依据式(1)计算所有相邻结点的距离：$\left|\right|n_i-n_j\left|\right|=\frac{1}{|{\mathrm{deg}}_i-{\mathrm{deg}}_j|+1}·min\{{\mathrm{deg}}_i,{\mathrm{deg}}_j\}·w_{ij},---\left(1\right)$其中，deg_i，deg_j分别表示结点n_i，n_j的度，min{x,y}表示取较小的一个值；w_ij表示给边(n_i,n_j)的权值；取所有边中距离的最小值d，将所有距离为d的边的端点进行重正化；在这里重正化采用的是最多最先处理的原则，即先处理拥有最短距离边数最多的点，先将此点的相邻最短的边所涉及的点进行重正化，即将其合并为一个点；重复此过程直到距离为d的边都被处理过；计算距离：d_k＝d_k‑1+d                            (2)和关联函数C(d)_k：$C{\left(d\right)}_k=\frac{1}{N^2}{\Sigma }_{i,j=1}^{N}H(d-||n_i-n_j|\left|\right)---\left(3\right)$其中，N为网络中结点的个数，n_i，n_j为网络中的结点；H(y)为阶跃函数(step function)，即$H\left(y\right)=\left\{\begin{array}{cc}1& y\ge 0\\ 0& y<0\end{array}\right.---\left(4\right)$令k＝k+1；步骤4、更新网络，具体为：经过步骤2的重正化后，每条边的权值w_ij则按下面的策略来计算：首先令所有的权值都为1；如果此时n_i和n_j经过上一步重正化前有s个边相连，则w_ij＝w_ij/s；若n_i和n_j有一个的度为1，且其所代表的点有m个，即它由m个点重正化而来，则w_ij＝w_ij*m；步骤5、输出结果：画图估计复杂网络的分形维数并给出其关联维数的值；网络的关联维数定义如下：$D_C=\underset{d\to 0}{\lim }\frac{\ln C\left(d\right)}{\ln d}---\left(5\right)$1)K个不同的社区{D_i}(i＝1…K)，其中对于2)一系列(C(d),d)点对的值及由此估计出的复杂网络分形维数D_c。