基于结构洞和度折扣的影响力最大化算法

在社会网络影响力最大化（IM）算法中,针对目前仅选取局部最优节点造成的影响范围较小的问题,综合考虑核心节点和结构洞节点的传播优势,提出了一种基于结构洞和度折扣的最大化算法（SHDD）。首先,该算法将结构洞思想和中心度思想互相融合应用到影响力最大化问题中,并找出能将结构洞节点和核心节点综合发挥最大传播作用的α因子,使得信息更大范围地扩散从而扩大整个网络的影响范围。其次,为突出两个思想融合的优势,将二度邻居的影响添加到结构洞评价标准中来选取结构洞节点。在不同规模的数据集上实验结果表明,与DegreeDiscount算法相比,SHDD在没有增加过多时间开销的同时扩大了影响范围;与基于结构的贪心（SG）算法相比,在聚类系数较大的网络中SHDD扩大了影响范围并降低了时间开销。SHDD在α因子取0.6时能最大限度地发挥结构洞节点和核心节点融合的作用并且在聚类系数较大的社交网络中能更加稳定地扩大影响范围。     

分层递阶的网络结构洞占据者挖掘及分析

结构洞是在社会网络信息传播中占据重要位置的一类关键节点。据研究,5%的结构洞控制着50%的信息传播。学者们研究了单一粒度网络下结构洞的挖掘方法及分析,然而很多网络存在分层递阶的多粒度结构特性,对分层递阶网络的结构洞挖掘和分析具有现实意义。因此,该文提出了一种分层递阶网络的多粒度结构洞挖掘方法HI-SH,并对不同粒度下的结构洞进行了分析。在该方法中,首先对网络进行多粒度社团划分,得到每一粒度下网络的社团;然后,根据两级信息传播理论,使用单一粒度下结构洞挖掘算法,挖掘每一粒度下top-k结构洞。在公用数据Topic16和真实数据上进行了实验,结果表明,网络的结构洞是动态变化的,单一粒度下的结构洞排名不能代表整个网络的结构洞排名。     

加权网络的结构洞挖掘算法

作为网络结构分析的重要概念,结构洞占据者在获取网络有效信息方面起着关键的作用。目前,研究者们主要针对无权网络研究挖掘其结构洞的方法,然而,实际网络中,边权对网络性能的影响起着重要作用。以加权网络为研究对象,以约束度为衡量指标,提出一种加权的结构洞挖掘算法--W_HIS算法（Weighted HIS Algorithm）。将提出的W_HIS算法应用到公用数据和实例数据,与已有的算法进行对比,验证了算法的有效性。实验结果表明,提出的算法对挖掘结构洞占据者效果相对较好。     

基于图结构特征分析的Top-k结构洞发现算法

结构洞通常指社交网络中处于信息扩散关键位置的节点,此类节点对社交网络舆情控制、影响力分析、信息传播等具有重要作用。为快速准确地找到社交网络中的结构洞,提出一种基于图最短路径增量的Top-k结构洞发现算法。通过计算并分析节点的图最短路径增量、连通分量个数和节点方差确定其结构洞属性值,并依据该属性值对节点进行排序,从而发现Top-k结构洞。同时,结合中介中心性算法进行节点的过滤与筛选,大幅降低算法的时间复杂度。在真实网络和不同规模LFR人工合成网络上的实验结果表明,与经典结构洞发现算法相比,该算法具有更高的结构洞检测效率。     

大规模数据下的社交网络结构洞节点发现算法研究

随着社会网络数据规模的递增,结构洞节点计算涉及的计算量呈几何级增长,如何构建有效的并行化算法并缩短算法运行的时间成为当前研究的难点。针对大规模数据量下结构洞节点发现算法的不足,利用并行化思想设计实现了基于MapReduce的结构洞节点发现算法。该算法通过DBLP,YouTube和Califonia公路网这3组规模不同的数据集在Hadoop集群上运行的实验结果表明,增加DataNode机器节点的数量能够缩短算法运行的时间,提高运行效率且具有良好的并行加速比和扩展性能。     

结构洞：虚拟学习社区信息获取行为研究

结构洞是社会结构的概念所内含的元素,用以研究人际关系网络的结构形态,分析怎样的网络结构能够给网络行动者带来更多的利益或回报,它包含了各种社会科学理论的思想。以虚拟学习社区中学习者的信息获取行为为例,从虚拟学习社区中存在的结构洞类型以及结构洞控制力、结构等位方面探究了结构洞对信息获取的影响,总结出了结构洞位置在控制信息分享方面的优势。     

基于引力因子的加权网络重叠社区识别算法

通过挖掘大数据来识别复杂社会网络上的社区,有利于对经济、政治、人口等方面的重要问题进行定量研究,社区的识别算法已经成为当前研究的热点问题。重点研究了重叠社区识别问题,提出了基于引力因子的加权复杂网络的重叠社区识别算法GWCR。该算法首先选取万有引力因子大的节点为中心节点,将节点与中心节点之间的引力因子作为衡量标准,并将节点归入社区引力因子大于某一阈值的社区,最后通过识别重叠节点来识别重叠社区。在3个真实网络数据集上的实验结果表明,与传统的重叠社区识别算法相比,GWCR算法划分的社区的模块度较高。     

基于加权合著网络的结构洞特征分析

科研合作日趋频繁,形成了大量复杂的网络结构,如引文网络、共引网络及合著网络等,合著现象也越来越多。结构洞的发现有助于科研合作中提高团队整体的创新能力。目前对于合著网络的结构洞分析多为无权网络,为了研究合著者的紧密程度在结构洞分析中的作用,以加权的合著网络为研究对象,将权重引入到约束度中,并对现有的结构洞算法--HIS算法进行改进,提出一种基于加权约束度的结构洞挖掘算法（W_CIHIS算法）。用约束度作为衡量指标,将W_CIHIS算法与HIS算法应用到公共数据进行对比,实验结果表明提出的算法有很好的效果。     

融合节点覆盖范围和结构洞的影响力最大化算法

影响力最大化是社交网络分析中的一个重要问题,旨在挖掘可以使得信息在网络中传播范围最大化的一小组节点（通常称为种子节点）。基于网络拓扑结构的启发式影响力最大化算法通常仅考虑某单一的网络中心性,没有综合考虑节点特性和网络拓扑结构,导致其效果受网络结构的影响较大。为了解决上述问题,提出了一种融合覆盖范围和结构洞的影响力最大化算法NCSH。该算法首先计算所有节点的覆盖范围和网格约束系数;然后通过覆盖范围增益最大原则选择种子节点;其次,若存在多个节点增益相同,则按照网格约束系数最小原则选取;最后,重复上述步骤直至选出所有种子节点。NCSH在不同种子数量和不同传播概率条件下,在六个真实网络数据集上均保持着优异的效果,在影响力传播范围方面,比同类的基于节点覆盖范围的算法（NCA）平均提高了3.8%;在时间消耗方面,比同类的基于结构洞和度折扣的最大化算法（SHDD）减少了43%。实验结果表明,NCSH能有效解决影响力最大化问题。     

一种基于局部扩展优化的重叠社区发现算法

挖掘复杂网络的重叠社区结构对研究复杂系统具有重要的理论和实践意义。提出一种基于局部扩展优化的重叠社区识别算法。 首先基于网络节点的聚集系数筛选种子节点,选取不相关的、局部聚集系数大的种子作为初始社区;然后采用贪心策略扩展初始社区,得到局部连接紧密的自然社区;最后检测并合并相似的社区,获得高覆盖率的重叠社区结构。在人工生成网络和真实网络数据集上的实验结果表明,与现有的基于局部扩展的代表性重叠社区发现算法相比,所提算法能在稀疏程度不同的网络上发现更高质量的重叠社区。     

强/弱连接对软件网络结构的影响*

抽取类级软件网络拓扑模型,提出用紧密度来测度网络中的强连接,用结构洞来刻画网络中的弱连接。由紧密度与度的相关性得出高度值节点周围一定存在强连接,低度值节点间不一定用强连接相关联;由中介度与结构洞的相关性得出网络中的弱连接与节点占据结构洞有关,无洞和全洞结构都不存在弱连接;利用K-近邻指标分析强/弱连接的分布特征,得出强连接具有网络中心性,而弱连接的中心性并不明显;通过逐步删除一定百分比的强/弱连接节点和边来对比分析它们对软件网络结构的影响,结果表明移去强连接可迅速破坏网络的连通性,而移去弱连接在一定范围内对网络结构影响并不大,但随着删除比例增多,网络的连通性和信息流动受到严重破坏。所得结论对度量和控制软件结构复杂性提供理论指导。     

面向属性网络的重叠社区发现算法

针对现实世界的网络节点中包含大量属性信息并且社区之间呈现出重叠特性的问题,提出了一种面向属性网络的重叠社区发现算法。融合网络的拓扑结构和节点属性定义了节点的密集度和间隔度,分别用于描述社区内部连接紧密和外部连接松散的特点。基于密度峰值聚类的思想搜索局部密度中心作为社区中心,在此基础上给出了非中心节点关于各个社区的隶属度的迭代计算方法,实现了重叠社区的划分。在真实数据集上进行了仿真实验,实验结果表明所提算法相对于LINK、COPRA和DPSCD能获得更好的社区划分结果。     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。     

基于LeaderRank的重叠社区发现算法

在真实的社交网络结构中常常存在着社区相互重叠的现象,发现社交网络中的重叠社区有利于研究网络特性,反映网络中的真实情况。针对多标签传播重叠社区发现算法COPRA存在的随机性,导致社区发现结果稳定性差等问题,提出一种结合节点重要性的标签传播算法。该算法首先采用LeaderRank计算出网络中各个节点的重要性,选择重要性高的节点进行团扩展作为标签初始阶段的预处理,采用合理的标签更新顺序以防止抵消预处理阶段的工作,后期引入贡献度来弱化标签选择阶段的随机性,在基准网络和真实网络上的实验结果表明本文算法提高了社区发现结果的质量。     

基于三支决策的非重叠社团划分

基于三支决策理论,提出了一种基于三支决策的非重叠社团划分算法（N-TWD）,该方法将初始聚类形成的重叠社团进行二次划分以形成最终的非重叠社团。N-TWD算法首先利用层次聚类形成有重叠的社团结构,将两个存在重叠的社团的左边社团中非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。然后,针对边界域中的节点,分别计算边界域中节点与正域和负域的社团归属度B_P、B_N进行二次划分。对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属,最终获得非重叠的社团结构。本文选取4个经典社交网络数据集和1个真实世界数据集对N-TWD算法进行了验证,相比较其他社团划分算法（GN、NFA、LPA、CACDA）,N-TWD时间复杂度较低,总体获取的社团模块度值更高。     

LPX: Overlapping community detection based on X‐means and label propagation algorithm in attributed networks

Traditional community detection methods in attributed networks (eg, social network) usually disregard abundant node attribute information and only focus on structural information of a graph. Existing community detection methods in attributed networks are mostly applied in the detection of nonoverlapping communities and cannot be directly used to detect the overlapping structures. This article proposes an overlapping community detection algorithm in attributed networks. First, we employ the modified X‐means algorithm to cluster attributes to form different themes. Second, we employ the label propagation algorithm (LPA), which is based on neighborhood network conductance for priority and the rule of theme weight, to detect communities in each theme. Finally, we perform redundant processing to form the final community division. The proposed algorithm improves the X‐means algorithm to avoid the effects of outliers. Problems of LPA such as instability of division and adjacent communities being easily merged can be corrected by prioritizing the node neighborhood network conductance. As the community is detected in the attribute subspace, the algorithm can find overlapping communities. Experimental results on real‐attributed and synthetic‐attributed networks show that the performance of the proposed algorithm is excellent with multiple evaluation metrics.