带源节点的快速社区发现算法

提出了一种改进的带源节点的CNM快速社区发现算法,用于含有部分已知社区属性节点的复杂网络的社区结构划分。算法中将这部分节点作为源节点,采用模块度增量最大化为目标函数对待划分节点进行聚合,并在取得最大全局模块度值时得到社区划分结果。以深圳市手机基站用户流量网络为例,将位于各规划城市中心的基站点作为源节点引入,对城市进行区域划分。结果表明,该算法不但能够发现基于各城市中心的服务边界,也能发现一些隐含的城市区域。     

基于局部思想的在线社区划分算法

为了快速准确地对在线社会网络进行社区划分,提出了一种基于局部思想的社区划分算法。该算法利用节点和社区聚集系数的性质,结合局部模块度将节点划分成相对独立的社区。算法运行时,只需要了解与目标节点相关的局部网络信息,时间复杂度相对较低,并且也可以用来对整个在线社会网络进行社区划分。利用该算法分别对Zachary空手道俱乐部网络和在线社会网络进行划分实验,得到满意的结果。     

基于局部语义聚类的语义重叠社区发现算法

语义社会网络是一种包含信息节点及社会关系构成的新型复杂网络,因此以节点邻接关系为挖掘对象的传统社会网络社区发现算法无法有效处理语义社会网络重叠社区发现问题。针对这一问题,提出基于局部语义聚类的语义社会网络重叠社区发现算法,该算法：1）以 LDA （latent Dirichlet allocation）模型为语义信息模型,利用 Gibbs 取样法建立节点语义信息到语义空间的量化映射;2）以节点间语义坐标的相对熵作为节点语义相似度的度量,建立节点相似度矩阵;3）根据社会网络的局部小世界特性,提出语义社会网络的局部社区结构 S‐fitness 模型,并根据 S‐fitness 模型建立了局部语义聚类算法（local semantic clusterm ,LSC）;4）提出可度量语义社区发现结果的语义模块度模型,并通过实验分析,验证了算法及语义模块度模型的有效性及可行性。     

基于矩阵分解的属性网络嵌入和社区发现算法

属性网络不但包含节点之间复杂的拓扑结构,还包含拥有丰富属性信息的节点,其可以比传统网络更有效地建模现代信息系统,属性网络的社区划分对于分析复杂系统的层次结构、控制信息在网络中的传播和预测网络用户的群体行为等方面具有重要的研究价值.为了更好地利用拓扑结构信息和属性信息进行社区发现,提出了一种基于矩阵分解的属性网络嵌入和社区发现算法(CDEMF).首先提出基于矩阵分解的属性网络嵌入方法,基于网络局部链接信息计算相邻节点的相似性,将其与属性接近度联合建模,通过矩阵分解的分布式算法得到每个节点对应的低维嵌入向量,即把网络节点映射为低维向量表示的数据点集合.接着提出基于曲率和模块度的社区划分方法,自动确定数据点集合中蕴含的社区数量,并通过对数据点集合聚类完成属性网络社区划分.在真实网络数据集上,将CDEMF方法与其他8种知名算法进行比较,实验结果表明CDEMF具有良好的性能.     

一种融合邻边属性的个人社交网络社区发现算法

针对传统智能进化社区发现算法通常存在弱化节点属性和容易过早收敛等问题,提出基于邻边属性群智能聚类的个人社交网络社区发现算法NLA/SCD。在融合邻边结构及其节点属性相似特性的基础上,定义社会蜘蛛优化算法的适应度函数,并将社区模块度增量作为算子迭代准则。在雌性和雄性个体的进化与交配过程中,利用适应度函数和模块度增量函数从局部和全局角度优化社区划分的寻优过程,以保持种群多样性并避免算法过早收敛。实验结果表明,NLA/SCD算法能有效识别属性信息多样的个人社交网络,且具有较高的运行速度和划分精度。     

复杂网络基于局部模块度的社团划分方法

提出了一种基于局部模块度的社团划分算法,该算法的基本思想是将具有最大综合特征值的节点作为初始节点,然后从候选集中找到使局部模块度Q达到最大值时所对应的候选节点,将此节点合并到该社团中,更新候选集合直至Q值不再增加,此时该社团形成.由于算法仅需要利用节点的局部信息,因此时间复杂度很低,并且通过综合特征值,找到聚类中心,从而使得聚类效果大大提高.通过社会学中经典的Zachary网络表明了该算法的可行性,并得到满意的结果.     

基于节点拓扑结构和属性的重叠社区检测算法

近些年来,网络中的重叠社区检测应用越来越广泛,这极大引起了人们的兴趣。通常重叠社区检测只考虑节点的拓扑结构信息,忽略了节点的属性信息,这可能会遗漏数据间的重要结构。本文提出了一种基于节点拓扑结构和属性相似度的局部社区检测算法。首先,计算出节点与社区之间属性相似度。其次,为挖掘内部紧耦合的社区,计算出能够表示耦合性的模块度增量。最后,通过融合多个已检测到局部社区,计算出隶属矩阵从而获取全局重叠社区结构。在三个有真实社区的数据集上的实验结果从内部指标模块度和与真实社区的比较验证了基于节点拓扑结构和属性相似度的重叠社区检测算法比目前基于节点结构的社区检测算法在效率和有效性上有所提升。     

复杂网络局部社区挖掘的节点接近度算法

为了准确、快速地发现大规模复杂网络中的局部社区,提出了一种基于节点接近度的局部社区发现算法。该算法以最大度节点作为起始节点,利用节点接近度和局部社区Q值不断搜索其邻居节点,将接近度最大的节点加入初始社区形成新的初始社区;同时,该算法也可以应用于复杂网络全局社区结构的划分。对2个典型复杂网络进行了局部社区挖掘分析,实验结果表明,该算法能够有效识别隐藏在实验网络中的局部社区。针对稀疏网络,该算法的时间复杂度为O（nlog（n））,n为网络节点数。     

基于资源分配指标的最大约束社区发现算法

在复杂网络中的社区发现一直受到广泛的关注,基于模块度最大化的方法是目前流行的社区发现技术。提出一种基于资源分配(RA)指标和多步贪婪凝聚策略的模块度最大化社区发现算法RALPA(Resource Allocation-based of Label propagation Algorithm)。该算法利用准确衡量节点间相似性的RA指标,通过最大约束标记传播模型使社区内部节点拥有较高的相似性,与社区外部的节点拥有较低的相似性。然后,通过多步贪婪凝聚策略将划分模块度增加最大的多对小社区进行合并。实验结果表明,该算法不仅避免了对节点更新顺序的敏感和易得到平凡解的问题,而且提高了算法的稳定性和社区划分的精度。     

基于信息扩散概率的二分网络社区划分算法

二分网络是复杂网络的表现形式之一,二分网络单侧节点的社区划分对研究复杂网络具有重要的实际意义.基于信息在网络中的扩散概率和模块度思想,本文提出了一个针对二分网络的社区划分聚类算法(IPS算法).该算法通过模拟信息在网络中扩散的过程,利用各个节点的信息量在网络中扩散后,每个节点收到其他节点的信息量作为社区之间合并的依据,并引入二分网络模块度作为社区划分优劣判断的依据.最后算法在典型网络上测试结果表明,该算法不仅能够精确的识别二分网络社区个数,而且可以获得高质量的社区划分结果.     

基于组合模型的局部搜索弱社团结构发现算法

针对复杂网络社团结构发现算法中全局模块度存在的分辨率缺陷问题,即不能发现很多实际存在的小社团,甚至发现的社团不满足普通意义上的社团定义,给出一种新型的多目标整数规划模型。结合弱社团定义、局部适应度和全局模块度标准,提出一种高效的启发式算法,发现网络的层次重叠社团。实验结果表明,该算法克服全局模块度的缺陷,能充分挖掘出小社团,具有较高的效率。     

改进的CNM算法对加权网络社团结构的划分

为了对可以反映网络结构局部重要性质的加权网络进行社团结构划分,延续广泛应用的社团结构分级聚类方法,改进Newman贪婪算法（CNM算法）。算法设计中引入点权和边权,并重新定义新的Q函数计算社团模块度,通过寻找Q函数峰值确定社团划分的最终结果。另外以股票价格波动相关性为加权边建立的加权网络为例进行算法检验,社团划分的结果验证了改进的CNM算法的有效性。与改进的GN算法、极值优化算法等划分效果进行比较分析后发现,改进算法在划分准确性及算法复杂度等方面都有明显的优势。     

复杂网络大数据中重叠社区检测算法

大数据时代互联网用户数量呈爆炸性增长,社交网络、电商交易网络等复杂网络规模快速发展,准确有效地检测复杂网络大数据中重叠社区结构对用户兴趣点推荐和热点传播具有重要意义。提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（Detecting Overlapping Communities over complex network big data）,时间复杂度为O（nlog²（n））,算法基于模块度聚类和图计算思想应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法。相对于传统重叠节点检测算法,对每个节点分析的频率大大降低,可以在较低的算法运行时间下获得较高的识别准确率。复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法。     

一种基于粗糙集的社区结构发现算法

提出一种基于粗糙集的社区结构发现算法。将信息中心度作为衡量节点之间关联度的标准,在处理社区间边界节点时引入粗糙集中的上下近似集概念。将网络中的各个节点划分到社区中,从而将复杂网络划分成k个社区,k值由算法自动选定,并通过模块度确定理想的社区结构。在Zachary Karate Club模型和College Football Network模型上进行验证,实验结果表明,该算法的准确率较高。     

基于权重信息挖掘社会网络中的隐含社团

社团结构是一种普遍存在于各类真实网络中的结构特性.挖掘网络的社团结构对于理解网络的功能与行为有着重要作用.然而,现有的各种社团挖掘算法仅仅基于网络拓扑结构信息,而忽视了蕴涵于真实社会网络边权信息中丰富的语义信息.目前普遍使用的基于模块性最大化的社团挖掘算法倾向于将小社团合并,这使得语义上丰富的小社团容易湮灭于基于拓扑结构信息所挖掘出的大社团中.而挖掘出这些隐含于大社团中的有着丰富语义内涵的小社团对于加深社会网络语义层面的理解有着重要作用.为此,提出一个接近线性复杂度的有权网络社团挖掘算法.通过充分利用权重信息,算法可以将社会网络划分为富含语义信息的粒度较细且相对较小的隐含社团.通过对基于DBLP作者合作网络的实证分析,证实了新算法的有效性和高效性.     

基于网络嵌入与局部合力的复杂网络社区划分算法

社区划分可以揭示复杂网络中的内在结构和行为动态特点,是当前的研究热点。文中提出了一种基于网络嵌入和局部合力的社区划分算法。该算法将网络的拓扑空间转化成欧氏空间,把网络节点转换成向量表示的数据点,首先基于重力模型和网络拓扑结构,提出局部合力和局部合力余弦中心性指标(Local Resultant Force Cosine Centrality,LFC),通过节点的LFC和节点间的距离来确定各个初始小社区的中心节点,然后将网络中其他的非中心节点划入与其最近的中心节点所在的初始小社区内,最后通过优化模块度的方法来合并初始小社区并找到最优的网络社区结构。在6个现实世界网络和可调参数人工网络上与6种知名社区划分方法进行比较,比较结果表明了新算法良好的社区划分的性能。     

改进的基于局部模块度的社团划分算法

针对大多复杂网络社团划分算法不能快速发现最优节点加入社团的问题,提出一种利用节点亲密度的局部社团划分算法。引入节点亲密度的概念量化社团与邻居节点的关系,按照节点亲密度由大到小选择节点加入社团,最后以局部模块度为指标终止局部社团扩展。在真实网络和人工仿真网络进行实验,并与基于信息压缩的随机游走算法等4种典型社团划分算法相比较,所提算法划分结果的综合评价指标(F1score)和标准化互信息(NMI)均好于比较算法。实验研究表明,所提算法具有较好的时间效率和准确度,适用于大规模网络社团划分。     

一种面向语义重叠社区发现的Link-Block算法

语义社会网络是一种由信息节点及社会关系构成的新型复杂网络,传统语义社会网络分析算法在进行社区挖掘时需要预先设定社区个数,且无法发现重叠社区.针对这一问题,提出一种面向语义社区发现的link-block算法.该算法首先以LDA模型为语义信息模型,创新性地建立了以link为核心的block区域LBT(link-block-topic)取样模型;其次,根据link-block语义分析结果,建立可度量link-block区域的语义链接权重方法,实现了语义信息的可度量化;最后,根据语义链接权重建立了以link-block为单位的聚类算法以及可评价语义社区的SQ模型,并通过实验分析,验证了该算法及SQ模型的有效性及可行性.     

基于结构相似度仿射传播的社团检测算法

复杂网络中普遍存在着一定的社团结构,社团检测具有重要的理论意义和实际价值。为了提高复杂网络中社团检测的性能,提出了一种基于结构相似度仿射传播的社团检测算法。首先,选取结构相似度作为节点之间的相似性度量,并采用了一种优化的方法来计算复杂网络的相似度矩阵;其次,将计算得到的相似度矩阵作为输入,采用快速仿射传播(FAP)算法进行聚类;最后,得到最终的社团结构。实验结果表明,所提算法在LFR(Lancichinetti-Fortunato-Radicchi)模拟网络上的社团检测平均标准化互信息(NMI)值为65.1%,要高于标签传播算法(LPA)的45.3%以及CNM(Clauset-Newman-Moore)算法的49.8%;在真实网络上的社团检测平均模块度值为53.1%,要高于LPA算法的39.9%以及CNM算法的47.8%,具有更好的社团检测能力,能够发现更高质量的社团结构。