基于顶点差异性的社团发现方法

摘要

基于顶点差异性的社团发现方法，包括如下步骤：步骤1为网络构建阶段，步骤11)为数据预处理过程：111)去掉无效数据；112)有效数据编号；步骤12)扫描得到并去掉不必要的分量的过程；通过一遍扫描数据得到当前所有分量，并且去掉较小的；步骤13)扫描各个分量得到各个分量的邻接矩阵：对每个分量进行扫描，根据数据点之间的联系得到邻接矩阵；步骤2为社团发现阶段，即运用差异性、边移除与贪婪方法得到社团网络中存在的社团结构，其具体步骤如下：包括初始化过程；计算顶点对之间的差异性；根据差异性发现网络中的社团结构；社团的合并；结束。本发明所得到的社团是原始网络的准确而自然的划分，并且提高了社团发现方法的性能。

主权项

基于顶点差异性的社团发现方法，其特征是包括如下步骤：步骤1为网络构建阶段，即将原始数据抽象成为在社会网络分析中的网络，其具体过程如下：步骤11)为为数据预处理过程：111)去掉无效数据：通过对现在实际数据的一次扫描，去掉数据中的不完整信息；112)有效数据编号：鉴于现实数据的多种多样，按顺序对所有的研究顶点进行编号；步骤12)扫描得到并去掉不必要的分量的过程；通过一遍扫描数据得到当前所有分量，并且去掉较小的，不必进行社团发现的分量，具体方法是从一个顶点出发找到其所在的分量，直到所有的顶点均被扫描；然后去掉大小未达到标准的分量；步骤13)扫描各个分量得到各个分量的邻接矩阵：对每个分量进行扫描，根据数据点之间的联系得到邻接矩阵；步骤2为社团发现阶段，即运用差异性、边移除与贪婪方法得到社团网络中存在的社团结构，其具体步骤如下：21)初始化过程：初始化过程中用到的量。初始归属向量V1＝(1，1，1...1)，评价标准Modularity的值Q＝0，Q的增量DQ初始值设为正无穷大，邻接矩阵W及其备份CW，使用Wxy与(CW)xy来表示W、CW中第x行，第y列的元素；步骤22)是使用差异性、边删除并结合贪婪方法来发现社团结构的过程，它又可以分为如下的几个步骤：221)利用CW进行差异性的计算：计算所有相邻顶点之间的差异性如下：引入以下两个量：Axy，表示顶点x，y之间的吸引力；Rxy表示顶点x，y之间的排斥力；如果用(CW)xy表示x，y之间的权值，定义： A xy = Σ s ∈ Γ ( x ) ∩ Γ ( y ) ( CW ) xs + Σ s ∈ Γ ( x ) ∩ Γ ( y ) ( CW ) ys R xy = Σ s ∈ Γ ( x ) - Γ ( y ) ( CW ) xs + Σ s ∈ Γ ( y ) - Γ ( x ) ( CW ) ys 于是对于相邻的顶点对x与y，二者之间的差异性如下计算： Φ xy = R xy R xy + A xy + 2 在计算中利用最大堆记录当前所有顶点对的差异性，二元组(x，y)记录当前差异性最大的顶点对；222)根据顶点差异性的值移除边的过程：令(CW)xy＝0，(CW)yx＝0。223)社团结构评估过程：判断是否有新的社团产生，通过计算Modularity值将新的社团结构与原有社团结构比较；224)判断是否有新的社团产生NewCommunityExists：空队列Queue，将顶点x加入Queue中，开始如下循环过程：在Queue不为空的情况下，取出队列头元素v，加入到集合Sold中，取网络中使(CW)uv＞0的所有顶点u，如果u尚未被访问，则加入到队列Queue中，队列元素计数currentCount的值加1；循环过程结束后，在向量Vk中找到顶点i所对应在的元素Vki，并在Vk中找到值为Vki的元素个数，记为originalCount，如果currentCount＝originalCount表示没有产生新的社团结构，评估过程终止，直接转入步骤221)来重新计算顶点之间的差异性；否则，表明产生了新的社团结构，需要依次进行以下步骤来到达步骤227)；225)产生新社团结构后更新归属向量过程UpdateVector，空队列Queue，n维零向量Vk+1＝(0，0，0...0)，顶点y加入Queue中，开始如下循环过程：在Queue不为0的情况下，取出队列头元素v，加入到集合Snew中，取网络中使(CW)uv＞0的所有顶点u，如果u尚未被访问，则加入到Queue中，并更新归属向量Vk+1：V(k+1)，j＝k+1；循环过程结束后，将Vk+1中为零的元素置为Vk中相应的元素值；226)计算新社团结构的Modularity的增量DQ：利用Sold与Snew中记录的顶点信息得到新产生的两个社团内部权值Told与Tnew，以及两个社团之间边的权值Tbetween，从而得到三者在所有的权值中所占的比例aold，anew与abetween，从而得到Modularity的增量DQ；227)利用DQ的值对当前的社团结构进行评价：如果DQ的值大于或等于0，则对当前的Q进行更新，即Q＝Q+DQ，并且令k＝k+1，然后转入步骤221)，否则直接转入步骤23)结束社团结构发现过程；23)社团合并过程MergeCommunity：将大小为1的社团合并到适当的社团中去；扫描最终的归属向量Vk，得到各个社团的大小向量Vsize，扫描向量Vsize，得到每个大小为1的社团及其所包含的顶点编号，放到集合S中；对于S中的任一元素v，进行如下过程：找到v所在的社团编号Cv，找到使(CW)uv＞0的所有元素u，以及其所在的社团编号Cu；找到社团Cw，使Cw中包含v的相邻顶点(即元素u)最多，合并Cv与Cw，同时根据顶点v与原始邻接矩阵CA对Q值及归属向量Vk做出更新；24)结束过程：根据归属向量Vk得到所有顶点的社团归属，根据Q值的大小对社团结构做出评价。