一种基于先验信息和网络固有信息的复杂网络社区检测方法

摘要

本发明属于进化计算和复杂网络社区挖掘技术领域，具体公开了一种基于先验信息和网络固有信息的复杂网络社区检测方法，主要用于复杂网络的社区划分问题。其过程为：构建网络邻接矩阵；使用邻接矩阵信息初始化种群；根据邻接矩阵固有的信息进行预处理操作，减少无效搜索；优化模块度函数Q；采用基因交叉操作和变异操作；使用基于变异和网络固有信息的局部搜索方法LSMM；使用评价函数NMI测试社区划分结果。本发明充分利用先验知识和网络邻接矩阵所包含固有信息对社区网络进行检测。本发明采用基于变异和网络固有信息的局部搜索算法，更有效的得到最优解。本发明方法比一般遗传算法能更好的发现真实世界网络和人工合成网络的社区结构。

主权项

一种基于先验信息和网络固有信息的复杂网络社区检测方法，其特征在于：包括如下步骤：1)构建待检测复杂网络对应的邻接矩阵A：将具体的网络抽象为由点集和边集组成的图G(V,E)，V表示节点的集合，E表示边的集合，图G(V,E)中节点与节点之间的连接关系存储在邻接矩阵A中，即如果图中节点i和节点j之间有边直接相连，则在邻接矩阵A中对应的元素A_ij＝1，否则A_ij＝0，邻接矩阵A中只有0和1两种元素值；所述的复杂网络是城市交通网络或电力网络；2)初始化种群Spop：种群个体的编码方式采用字符串编码方式，对于一个个体G，G表示为一个正整数串，G＝[g₁,g₂,...,g_N],其中，N为节点的总数目，g_i是一个正整数，g_i为个体G的一个基因，i∈{1,2,...,N}，表示节点i属于g_i类，如果g_i＝g_j，且i≠j，则他们属于同一个社区划分，否则他们属于不同的社区；为把社区划分问题转化为寻找适应度最好的个体，将一个个体对应一种社区划分；在初始化时，把真实网络的真实社区数目label_max作为先验信息，同时利用网络邻接矩阵固有信息对种群进行初始化；当一个个体初始化时，每一个基因随机为该基因对应节点的邻居节点的基因值；如果该基因对应的邻居节点还未被初始化，那么随机为一个在[1,label_max]范围内的一个正整数，它的邻居节点是指和它有边直接相连的节点集合；随机产生popsize个上述种群个体，popsize为需要初始化的种群个体数目；3)对产生的初始种群采取预处理操作：对于种群Spop中任意一个个体G＝[g₁,g₂,...,g_N]，把个体G依次进行如下操作：把个体G＝[g₁,g₂,...,g_N]中g₁到g_N依次更新为其邻居节点中社区标签值出现最多的标签值，并且每个节点对自身标签的更新不受其他节点的影响；4)对种群Spop的所有个体计算适应度函数模块度Q；5)精英保存策略：找到并保存种群Spop中适应度值f最大的个体，也就是保存种群的最优个体；6)种群选择操作：从种群Spop中找出popsize个个体用于进行下交叉变异操作；选择操作采用锦标赛法，操作方法是，随机的从种群Spop中选取两个个体，比较适应度函数Q值的大小，适度值大的个体被选择，选取popsize次，得到popsize个个体；7)种群交叉操作：从种群Spop中任意选取两个个体A和B，以概率p_c进行交叉操作；对于进行交叉的两个父代个体A和B，随机的选择两个点i,j,i≤j≤N,N是网络中节点的总数目，以等概率进行选取三个操作中的一个进行交叉操作：交换个体A和个体B中第1个到第i个基因；交换个体A和B中第i个到第j个基因；交换个体A和B中第j个到第N个基因；8)种群变异操作：对于种群Spop，popsize个个体逐个进行变异操作；具体操作为：对于任意一个个体G＝[g₁,g₂,...,g_N]，从g₁到g_N以概率p_m进行变异，随机的把g_i变异为节点i的邻居节点中其中一个邻居节点的基因值；9)局部搜索算法：采用基于变异的局部搜索方法LSMM；LSMM方法的主要步骤如下，首先在一代中，把种群的popsize个个体按适应度值进行从大到小的顺序排列，对其中前个个体进行局部搜索；局部搜索过程中，对每一个个体的每一个基因找到该基因节点对应的所有的邻居节点的不同的基因值，并且存储它们，把出现次数最多的基因值替换原有的基因值；10)对种群Spop的所有个体计算适应度函数模块度Q；11)重复(4)到(10)直到迭代次数达到G_max为止，其中G_max为种群迭代次数。