基于个人意愿的社会网络团体结构与信息检测方案

个人意愿对于形成网络社团和传播信息有着重要的影响力,因此本文提出一种基于个人意愿的社团结构与信息检测方案.该方案中的社团检测算法初次检测以融入节点属性的模块度,再次检测以兴趣度并能发现重叠社团,最后精细检测以个人意愿,本文社团检测算法（ε_CSDA）较之前的算法更有效的是可以发现重叠社团;同时,该方案建立的信息传播模型在指数模型基础上构建边特征向量（边属性）、节点特征向量（节点属性）和意愿向量（用户意愿、社团意愿和节点意愿）,并以传播概率和传播延迟构建模型基本关系,从而使得该模型实现了基于个人意愿的信息传播.实验结果表明,加入个人意愿的社团检测和信息传播方案,能够保证社团检测的有效性和实用性,能够实现用户间信息传播的主动性和可靠性.     

基于影响力与种子扩展的重叠社区发现

社区发现作为复杂社交网络中一个重要的研究方向.针对目前基于种子节点的算法在种子选取与扩展等方面的不足,提出了一种基于影响力与种子扩展的重叠社区发现算法（Influence Seeds Extension Overlapping Community Detection,简称i-SEOCD算法）.首先,利用节点影响力策略找出具有紧密结构的种子社区.其次,从这些种子社区出发,计算社区邻居集节点与社区的相似度,并取出相似度超过设定阈值的节点.然后,采用优化自适应函数的策略来扩展社区.最后,对网络中的自由节点进行社区隶属划分,进而实现了整个网络的重叠社区结构挖掘.在真实社交网络和人工生成网络上实验表明,i-SEOCD算法能够准确、快速地发现复杂网络中的重叠社区结构.     

面向大规模网络的快速重叠社团挖掘算法

重叠社团在社交网络大数据中普遍存在.针对现有重叠社团挖掘算法易将重叠区域错误地划分为独立的社团且计算复杂的问题,提出了一种基于局部信息度量的快速重叠社团挖掘算法（Local information based Fast Overlapped Communities Detection,Li-FOCD）.首先,为节点定义局部信息度量指标——社团连接度和邻居连接度,建模节点与社团的关系,缩小了计算范围;然后,每次并行地迭代执行缩减、扩展、去重等操作,并更新局部度量指标,通过松弛每次迭代的终止条件,发现近似最优社团集合而不是最优社团,最终算法复杂度为O（m+n）.基于真实的大规模社交网络数据的试验分析表明：与当前流行的重叠社团挖掘算法相比,Li-FOCD在不损失检测质量的前提下,大幅提升了计算效率.     

模块度优化启发式算法应用

模块度优化的启发式快速算法常常用来检测复杂网络中的社团结构.较之其余的社团检测方法,该算法在计算时间上更具优势,而且用模块度衡量发现检测社团的质量很高.运用模块度优化启发式算法划分空手道俱乐部网络、大学足球俱乐部网络和区域贸易网络等,并对其结构和功能做出一定的分析.特别地,针对贸易网络中自由贸易区往往表现为一个社团的特点,以221个国家或地区为研究对象,对贸易协定与地域之间的关系做了大量的实证研究.首先,从世贸组织网站上采集了区域贸易协定中国家之间贸易的数据;其次,通过模块度启发式算法进行社团划分,共得出7个主要的贸易区,其中欧盟自由贸易区的社团表现极为明显;最后,从社团结构的表现形式推断实际区域间的贸易情况.     

复杂网络社团结构划分方法及其应用

许多实际的复杂网络都具有明显的社团结构,整个网络的功能实现是网络中各社团相互联系作用的结果。文章分别使用Girvan-Newman算法和Newman快速算法对实际的复杂网络进行社团划分。仿真结果显示,使用两种算法对网络进行社团划分时,都能得到清晰的社团结构,使用GN算法得到的社团数目小于使用NF算法得到的社团数目。NF算法的运行速度明显比GN算法的模块度要快。     

完全子图的邻域重叠社团结构探测

为了能够更准确地对邻域重叠网络进行社团结构探测,研究人员对基于完全子图的社团探测算法进行了改进。在合并完全子图团簇时,计算每一对完全子图的重叠节点个数,设置合并完全子图的阈值,如果大于阈值,则合并。在处理不在团簇内的其他节点时,采用按照比例系数大小来划分规则进行划分。算法应用5-空手道俱乐部和科学家合作网当中,验证算法可以更准确地探测邻域重叠社团结构。     

基于双编码的重叠社团检测多目标优化方法

近年来,多目标进化方法已被广泛应用于重叠社团检测问题并取得了较好的社团划分性能.如何设计合适的个体编码以及进化策略是提高基于多目标进化重叠社团检测算法性能的重要因素.为此,本文设计了一种双编码表示方法对非重叠社团结构和重叠点分别进行编码,能够有效解码得到重叠社团结构.在双编码表示的基础上,本文提出了一种基于双编码的重叠社团检测多目标优化方法(DRMOEA).在DRMOEA中,为了获得好的初始个体并提高算法检测性能,本文提出了一种基于社团边界点的初始化策略.除此之外,针对双编码中的重叠点编码部分,本文提出了基于精英个体边界点的交叉策略,该策略利用社团边界信息引导种群向好的方向进化,从而有效提高了算法的检测性能.最后,在9个真实世界网络上的实验结果表明DRMOEA算法优于其他5个代表性重叠社团检测算法.     

一种基于Jaccard相似度的社团发现方法

在复杂网络中自动发现社团具有重要的实际应用价值。本文提出一种基于Jaccard相似度的社团发现方法,首先使用结点的相似度寻找优先邻居结点,再从优先邻居结点中获得最佳邻居结点,最后将互为友好结点的两个结点合并,最终得到若干个结点的组成小社团,然后利用CNM算法凝聚小社团,完成社团发现聚类。实验表明本算法执行时间缩短,所发现社团模块度增加,是一个有效的社团发现算法。     

大规模复杂网络下重叠社区的识别

随着网络规模的不断扩大,经典的复杂网络重叠社识别算法已不能高效处理现有的大规模网络图数据.本文在GraphLab并行计算模型上提出了基于重要节点扩展的重叠社区识别算法DOCVN (Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab).算法选取网络中PageRank值大的节点作为重要节点,计算其他节点归属于重要节点的节点归属度,并以重要节点为中心形成核心社区及扩展社区,最后根据重要节点间的连接紧密度合并核心社区及扩展社区,并计算出每个节点在所属社区里的节点重要度,实现了大规模网络的重叠社区识别.实验表明该算法与PD (Propinquity Dynamics)等现有并行算法相比更能有效地识别大规模网络的重叠社区结构.     

基于稠密子团和边聚类系数的局部社团挖掘算法

发掘复杂网络的社团结构,有助于深入理解网络结构属性及其功能重要性。本文通过定义稠密子团,结合边聚类系数和局部模块度,提出一种DIDE社团挖掘算法。该算法通过选取稠密子团作为初始聚类团,利用边聚类系数扩张该稠密子团,最大化局部模块度值来生成社团结构。在计算机生成网络、三社团网络、Zachary网络和美国足球俱乐部网络上进行社团划分,验证该算法的可行性和有效性。     

Set pair three-way overlapping community discovery algorithm for weighted social internet of things

There are many problems in Social Internet of Things(IoTs), such as complex topology information, different degree of association between nodes and overlapping communities. The idea of set pair information grain computing and clustering is introduced to solve the above problems so as to accurately describe the similarity between nodes and fully explore the multi-community structure. A Set Pair Three-Way Overlapping Community Discovery Algorithm for Weighted Social Internet of Things (WSIoT-SPTOCD) is proposed. In the local network structure, which fully considers the topological information between nodes, the set pair connection degree is used to analyze the identity, difference and reverse of neighbor nodes. The similarity degree of different neighbor nodes is defined from network edge weight and node degree, and the similarity measurement method of set pair between nodes based on the local information structure is proposed. According to the number of nodes' neighbors and the connection degree of adjacent edges, the clustering intensity of nodes is defined, and an improved algorithm for initial value selection of k-means is proposed. The nodes are allocated according to the set pair similarity between nodes and different communities. Three-way community structures composed of a positive domain, boundary domain and negative domain are generated iteratively. Next, the overlapping node set is generated according to the calculation results of community node membership. Finally, experiments are carried out on artificial networks and real networks. The results show that WSIoT-SPTOCD performs well in terms of standardized mutual information, overlapping community modularity and F1.     

复杂网络的重叠社区及社区间的结构洞识别

大数据环境下如何有效地、准确地识别复杂网络的重叠社区是近年来学者关注的重点.本文提出一种基于多标签传播方式MLPS（Multiple Label Propagation Strategy）的重叠社区识别算法,该算法首先利用影响力最大化模型选取初始种子集合并赋予它们唯一的标签,然后采用结点间的相似性和影响传播特性共同作用于标签的传播迭代过程,迭代停止后将具有相同标签的结点划分为同一社区.通过合成网络和真实网络的实验验证了MLPS算法具有较高的准确度和模块度,且具有接近线性的时间复杂度.另外,在对MLPS算法输出的重叠结构进行分析的基础上,本文提出社区间的结构洞识别算法SHCDA（Structural Holes Between Communities Detection Algorithm）,该算法通过分析重叠结构和重叠结点的位置特征,计算重叠结点作为结构洞的得分,最后输出top-k结构洞.本文在不同特性的数据集上进行实验,结果证明了SHCDA算法具有最好的准确度.     

基于隶属度的社会化网络重叠社区发现及动态集群演化分析

社会化网络中节点的复合属性可能为临时或过时状态,并且节点拥有一定能力维持固有状态,所以不可单纯依据新增数据或节点现有特征确定社区划分.本文提出可重叠社区发现算法及集群动态更新方案,根据网络历史数据分析节点对原始集群的隶属程度,并结合新增数据确定节点变化趋势,实现网络结构分析及社区动态更新.本文分别在不同数据集中测试聚类效果,实验结果证明算法既保持对新增数据的敏感度,也防止了节点短暂特征或节点维持固有状态的能力对划分结果的负面影响.     

基于传染病模型的LPA特征阀值社团划分方法

社团结构划分对于分析复杂网络的统计特性非常重要.在非均匀社交网络的信息传播中,社团结构划分更是一个广泛关注的研究热点,相关研究往往侧重于研究紧密连接的社团结构对于信息传播所产生的关键影响.传统社团划分方法大多基于点和边的相关特性进行构建,如标签传播算法LPA（Label Propagation Algorithm）通过半监督机器学习方法,基于网络节点标签的智能交换和社团融合过程进行社团划分,但运行效率较低.为提高LPA类算法的运行速度,使其快速收敛,并提高社团划分精度,特别是重叠社团划分精度,针对LPA算法划分中的低运行效率和低融合收敛速度,本文从标签传播的网络连接矩阵本质出发,将该矩阵的最大非零特征值与网络标签信息传播的阀值相结合,提出了新的基于传染病传播模型的社团划分方法（简称ESLPA算法,Epidemic Spreading LPA）.通过经典LFR Benchmark模拟测试网络、随机网络以及真实社交网络数据上的算法验证,结果表明该算法时间复杂度大幅优于经典LPA算法,在重叠社团划分上精确度优于基于LPA模型的经典COPRA算法,特别是在重叠社团较明显时,划分精度接近精度较高GA、N-cut和A-cut算法,明显优于GN、FastGN和CPM等经典算法.     

基于归属不确定性的变规模网络重叠社区识别

 拓扑势理论是一种新的复杂网络社区识别理论.针对该理论和方法存在的应用范围不明确和社区重叠节点数量过少等问题,提出基于归属不确定性的变规模网络重叠社区识别方法.在证明拓扑势熵最小值点存在性的基础上,该方法通过提出重叠节点社区归属不确定性测度以及变规模社区的概念和思想,实现社区的有效识别.通过实验验证了该测度的合理性和有效性.实验结果表明,该方法不但具有识别变规模重叠社区的能力,而且还可获得与拓扑势方法相当的社区识别效果.     

Overlapping community detection in complex networks based on multi kernel label propagation

In view of the strong randomness and pre-setting the related threshold of traditional overlapping community detection method based on label propagation,overlapping community detection in complex networks based on multi kernel label propagation (OMKLP) was proposed.Evaluation model of kernel nodes was proposed after analyzing the node's degree and local covering density of nodes and their neighbor nodes.And on this basis,the detection method of local kernel nodes was also presented.Based on local kernel nodes,a new asynchronous label propagation strategy ori-ented to overlapping community was proposed,which can rapidly distinguish inner nodes and outer nodes of communi-ties so as to obtain overlapping community structure.The analysis method of overlapping nodes was proposed to increase the accuracy of detecting overlapping nodes.Without any prior knowledge,only on the basis of the basic network infor-mation (nodes and links),the algorithm can detect the structure of overlapping communities accurately.Therefore,it ef-fectively solved the defect of the traditional label propagation algorithm.The algorithm was tested over benchmark net-works and real-world networks and also compared with some classic algorithms.The experiment results verify the valid-ity and feasibility of OMKLP.     

融合节点分析与边分析的复杂网络社区识别算法

针对边社区识别与节点型社区识别两类算法在识别社区过程中均存在相应缺陷,影响复杂网络社区识别质量的问题,提出融合节点分析与边分析的复杂网络社区识别（CDHNE）算法。该算法首先运用边在网络中较为稳定的特点,在算法执行初期通过边社区识别构建较为准确的社区结构;然后利用节点较为灵活的特点,在边社区形成后,对边社区的边缘进行精确识别,更准确地识别出复杂网络中的社区结构。在计算机生成网络实验中,当网络的社区结构逐渐变得模糊、重叠节点数量与重叠节点归属社区数量不断增加时,CDHNE算法的社区识别精度较传统算法平均提高10%,在重叠节点识别精度上较传统算法平均提高15%;在真实网络实验中,算法识别的社区结构紧密度较好,特别是面对拥有十几万个节点的大规模网络时,CDHNE算法高质量地完成了识别任务,EQ值达到0.412 1。实验结果表明,CDHNE算法在运行稳定性和处理大规模网络方面具有优势。