一种基于PageRank算法的社区划分方法

摘要

本发明提供了一种基于PageRank算法的社区划分方法,属于复杂网络社区划分技术领域,该发明将PageRank算法的随机游走性质,量化为顶点间关系程度矩阵,将PR值迭代向量升维至能量分布矩阵,进而由顶点间关系程度来划分社区。具有记录内容详细、运算简便等优点，在网络结构分析、邮件鉴别、文档聚类、谣言传播、信值传播等方面有着广泛的应用前景。

主权项

一种基于PageRank算法的社区划分方法，包括步骤如下：步骤S1：根据N维原始网络图G的顶点和边的关系，求得原始网络图G的邻接矩阵D，如果从顶点i到顶点j存在边，则D_ij＝1，否则D_ij＝0；步骤S2：根据邻接矩阵D，求得原始网络图G的转移概率矩阵P，其中$P_{\mathrm{ij}}=\frac{D_{\mathrm{ij}}}{\underset{k=0}{\overset{N-1}{\Sigma }}{D}_{\mathrm{ik}}};$步骤S3：初始化能量矩阵A，所述能量矩阵A的第i行是当前时刻顶点i沿出度流出的能量值，第j列是当前时刻从其他点流入顶点j的能量值，初始时刻的能量矩阵为A₀；步骤S4：根据迭代公式A_n＝A_n‑1P，求得第n时刻的能量矩阵A_n；步骤S5：将能量矩阵A_n的对角线元素置零；步骤S6：利用“出度占比最大法”，在能量矩阵A_n中找出应当合并的顶点对(i，j)，并将顶点对(i，j)按照求解顺序存入序列List中；步骤S7：利用“行max列avg合并法”，将步骤S6中顶点对(i，j)对应的能量矩阵A_n中i行j行合并，i列j列合并，使得A_n降低1个维度；步骤S8：判断能量矩阵的维度是否为0，如果不为0，则继续执行步骤S6，如果为0，则执行步骤S9；步骤S9：根据顶点对序列List，建立顶点合并树，并计算每次合并的模块度Q值,其中n_c是划分的社区个数，m是原始图中的边总数，l_c是某个社区C中顶点间相互连接的边数，d_c是C中顶点度数之和；步骤S10：比较每次合并的Q值，选择Q值最大的合并方案，得到社区划分结果。