一种基于多网络模块度的社团发现方法

摘要

本发明公开一种基于多网络模块度的社团发现方法，首先提出了多网络的零模型，并在其基础上进一步提出了适用于多网络的，功能函数多网络的模块度；并在多网络模块度的基础上，提出了基于多网络模块度的快速社团发现方法，并验证了该方法的有效性，本申请的方法具有如下优点：采用网络配置的思想构建了基于节点冗余度的多网络零模型，保证零模型与原网络具有相同节点数、网络数、节点冗余度分布；提出多网络模块度，一种全新的衡量多网络社团结构的功能函数，为多网络社团评价提供了新方法；在多网络模块度的基础上，提出了基于多网络模块度最大化的快速社团发现算法，降低了求解多网络模块度的最大值时间复杂度。

主权项

一种基于多网络模块度的社团发现方法，其特征在于，包括：S1、计算多网络模块度，具体包括以下分步骤：S11、采用多个邻接矩阵表示多网络，具体为：MN＝{A₁,A₂,…,A_i,…,A_M},i≤M；其中，M表示网络个数，A_i表示第i个网络的邻接矩阵；S12、确定节点冗余度连接关系矩阵，将所有网络的邻接矩阵相加得到节点冗余度连接关系矩阵；表达式如下：$W=\underset{i}{\Sigma }{A}_i,i\le M;$其中，W表示节点冗余度连接关系矩阵，矩阵W中的每一行或每一列表示与该节点相连的各条边在网络中出现的次数，i表示邻接矩阵的序号，且i＝1,2,…,M；S13、根据步骤S12确定的节点冗余度连接关系矩阵，计算节点冗余度；表达式如下：$r_k^m=|w_{jk}=m+1|,w_{jk}\in W,0\le m<M;$其中，w_jk为多网络节点冗余连接关系矩阵W中的元素，表示节点k与节点j之间的连接边数，表示节点k的m阶冗余度；S14、根据节点冗余度构建多网络1阶零模型；S15、根据步骤S14构建的多网络1阶零模型，计算多网络模块度；S2、根据步骤S1计算得到的多网络模块度对多网络中社团进行划分；具体包括以下分步骤：S21、初始时将多网络中每个节点视为一个社团；S22、遍历多网络中每个节点z，找出所有与之相连的节点，并对每个相连的接点计算节点z加入该相连的节点所在社团的多网络模块度增量；S23、找出多网络模块度增量最大值所在的社团，将节点z添加至该社团；S24、重复步骤S22至步骤S23，直至社团个数不再变化；S25、将由步骤S22至步骤S24划分出的社团看作新的节点，重复步骤S22至步骤S24，直至所有新的节点的多网络模块度增量小于或等于0时，结束。