基于小波去噪的有向加权社团发现研究

目前大部分社团发现方法都是针对无向无权图,但实际的社会媒体中的社团内部个体交互过程可以抽象为一个有向加权图,并且权重中含有大量的噪声.为解决有向加权社团的划分问题,本文提出一种基于非负矩阵分解(Nonnegative matrix factorization,NMF)可去噪声的社团发现方法.该方法通过小波阈值去噪对社会网络数据进行去噪处理,结合有向加权的非负矩阵分解算法对去噪后的数据集进行社团发现,准确找出社团结构.在社会媒体的实验数据集和标准数据集上的实验结果表明,该算法针对带噪声的有向加权图社团发现问题具有良好划分性能,SNR为15时,在Lesmis数据集上的社团划分准确率达到96％,划分模块度值提高了29％.本文为解决带噪的有向加权的社会网络数据提供了切实有效的处理方法.     

一种基于相对关系亲密度的局部社团发现算法

在复杂网络研究中,社会网络中的社团发现,对商业营销、疾病传播控制等具有实际意义.目前许多研究针对于全局网络进行社团挖掘.挖掘算法因其较高的复杂度往往不适用于动态、大型网络.针对某个点或者某个区域的局部社团挖掘成为了近期的研究热点.为此提出了一种新的相对关系亲密度的计算方法,并与已有算法思想结合,形成了一种新的局部社团发现算法,提高了算法性能.基于已知社会网络、随机测试网络的实验证明了算法的有效性.     

DBSCAN算法在电子邮件网络社团发现中的应用

针对电子邮件复杂网络中的社团发现问题,将具有良好聚类性能的DBSCAN算法引入电子邮件网络社团发现。基于对该算法的分析,研究了电子邮件网络社团发现的系统架构及算法实现流程。最后通过对安然邮件语料集的测试验证了DBSCAN算法在社团发现中的可行性。     

基于社团强度系数的社团结构发现算法

社团结构是复杂网络普遍存在的拓扑特性之一.为了将复杂网络中的社团结构有效地划分出来,在对强社团定义的基础上,引入社团强度系数的概念,提出了一种基于社团强度系数的社团结构发现算法.该算法具有较低的时间复杂度,通过不断寻找网络最大度数的节点及其邻居节点,计算其社团强度系数来衡量社团如何划分.主要针对Zachary网络和Dolphin网络等进行了仿真实验,结果表明该算法具有较高的社团划分准确度、较好的敏感性和良好的可扩展性,充分验证了其可行性和有效性.     

基于有向赋权图的垃圾邮件社团发现算法

本文在有向赋权邮件网络的基础上,针对垃圾邮件的特征,分析邮件发送者和接收者的关系,通过社团密度这一度量函数,对有向赋权邮件网络进行社团结构分析,以准确确定社团结构与形式,该算法另一优势是可发现重叠社团。     

近似线性时间的社团结构动态演化挖掘算法

探测网络社团结构对于分析、设计复杂的自然或工程网络至关重要,然而现有的探测技术主要依托于最优化和启发式算法,不能兼顾计算效率和准确性。因此提出了一种基于演化迭代技术的动态社团探测算法,它能准确高效地发现网络中的社团结构。首先引入了一个离散时间的动态系统,通过描述社团划分收敛到特定指标最优的演化轨迹来确定社团划分。接着提出了一个一般化的指标函数,以确定网络中最优的社团数量及最稳定的社团结构。该指标函数极具概括性,改变相应的参数即可引申到各种已广泛应用的指标函数。针对参数选择的困难,利用图生成模型自动确定社团划分的指标函数。此算法效率很高,计算复杂度与稀疏网络中的节点数量呈近似线性关系。最后,在人工和真实网络中进行了大量的仿真实验来测试算法表现,结果显示所提算法能够揭示很多有价值的信息。     

基于信号传递与层次聚类的社团发现算法

社团是社会网络的一个重要特征,社团发现是近年来研究的热点问题之一。通过在复杂网络上传递信号,获得各节点对网络的影响向量,从而把网络中节点的拓扑性质转化为代数空间上向量的几何关系,然后用结合模块度的层次聚类挖掘社会网络中的社团结构。该算法优点是不需要预先知道社团的数量或社团内节点的数量,用Zachary空手道俱乐部网络、大学足球赛网络以及海豚关系网络的数据进行验证,该算法划分的社团准确性超过了Newman的结论。     

基于节点内聚系数的局部社团发现算法

为了能够快速有效地发现复杂网络中的局部社团,提出一种基于节点内聚系数的局部社团发现算法。该算法选取最大度节点作为起始社团,不断搜索其邻居节点,将满足条件的节点不断加入起始社团从而形成新的社团。在不同规模的真实网络数据集和人工合成数据集上进行实验,并与其他三种局部社团发现算法进行社团划分效果的对比。实验结果表明,该算法能够在较短的运行时间内保持较高模块度来识别复杂网络中的局部社团结构,更适合于大规模复杂网络的社团结构挖掘。     

基于社团密度的社团发现算法

发现社团结构是研究复杂网络的重要前提,目前社团发现算法研究存在两个较为严峻的问题：评价函数单一和经典算法时间复杂度过大并且无法发现小粒度的社团。针对上述问题,本文首先提出了一种合理的发现算法评价函数,即社团完整度,实验证明,与经典的模块度函数 相比,社团完整度函数能够更合理地评价社团划分质量且社团完整度函数的灵敏度高于模块度函数;其次,本文提出了基于社团密度的社团发现算法,实验证明,该算法不仅可以发现小粒度的社团结构,随着网络节点数和边数的增加BDA算法在时间复杂度方面也具有明显的优势。最后,本文尝试将BDA算法应用在科学合作者网络并得到合理的社团结构。     

基于最大节点接近度的局部社团结构探测算法

针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O(kd)。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。     

Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network

Community structure is an important property of network. Being able to identify communities can provide invaluable help in exploiting and understanding both social and non-social networks. Several algorithms have been developed up till now. However, all these algorithms can work well only with small or moderate networks with vertexes of order 104. Besides, all the existing algorithms are off-line and cannot work well with highly dynamic networks such as web, in which web pages are updated frequently. When an already clustered network is updated, the entire network including original and incremental parts has to be recalculated, even though only slight changes are involved. To address this problem, an incremental algorithm is proposed, which allows for mining community structure in large-scale and dynamic networks. Based on the community structure detected previously, the algorithm takes little time to reclassify the entire network including both the original and incremental parts. Furthermore, the algorithm is faster than most of the existing algorithms such as Girvan and Newman＇s algorithm and its improved versions. Also, the algorithm can help to visualize these community structures in network and provide a new approach to research on the evolving process of dynamic networks.     

社会语义网社区发现标签传递算法研究

针对在线社会网络的特性和现有社区发现算法的不足,提出一种基于语义网技术的在线社会网络社区发现算法ISLPA(Improved Semantic Label Propagation Algorithm),即一种适用于大规模在线社会网络的社区发现和标识算法。ISLPA算法对语义标签算法SemTagP进行改进,在社区划分过程中将在线社会网络视为有向加权图,通过语义网和社会化标签技术,充分结合在线社会网络丰富的语义信息和网络拓扑特征进行社区划分。ISLPA算法不需要预先设定社区数量和大小,就能实现社区发现,并能根据标签自动识别划分的社区。算法接近线性时间复杂度,具有较高的效率。通过实验表明,ISLPA算法能有效划分和标识真实在线社会网络。     

一种时序有向网络中的链路预测方法

真实网络大多是有向的，且网络结构随时间动态变化，传统的链路预测方法大多适用于无向网络，其分析方法不能有效挖掘真实网络中的信息。针对以上问题，提出了一种基于归一化AA和LAS的时序有向的链路预测算法，该算法基于共同邻居、节点度属性及局部社团相似性，为每个链接分配时间影响因子并将其引入NALAS指标进行计算，考虑了网络有向性和网络历史结构的影响。在真实社会网络数据集上对该算法进行了仿真并与Salton、Jaccard等算法进行对比。结果表明，提出的算法与其他算法相比，预测精度得到了提高，说明该算法可以有效地在时序有向的社会网络中进行链路预测。     

动态加权网络中的演化社区发现算法研究

在动态网络中发现社区结构是一个非常复杂而有意义的过程,可以更好地观察和分析网络的演化情况。针对动态加权网络中的社区发现问题,提出了一种结合历史网络社区结构的算法,叫做动态加权网络中的演化社区发现算法（ECDA）。该算法分为两步：结合历史社区和网络结构信息,计算当前时间跳的输入矩阵;然后通过该输入矩阵计算得到结合历史时间跳信息的社区划分结果。该算法有以下优点：可以自动发现动态加权网络中每个时间跳的社区结构;对网络结构的变化和社区结构的变化具有较高的敏锐性。在人工数据集和真实数据集中进行了实验,实验结果证明该算法可以有效地发现动态加权网络中的社区结构,与其他算法相比具有较好的竞争力。     

基于重叠社区搜索的传播热点选择方法

随着社交网络的蓬勃发展,信息传播问题由于具有广泛的应用前景而受到广泛关注,影响力最大化问题是信息传播中的一个研究热点.它致力于在信息传播过程开始之前选取能够使预期影响力达到最大的节点作为信息传播的初始节点,并且多采用基于概率的模型,如独立级联模型等.然而,现有的影响力最大化解决方案大多认为信息传播过程是自动的,忽略了社交网站平台在信息传播过程中可以起到的作用.此外,基于概率的模型存在一些问题,如无法保障信息的有效传播、无法适应动态变化的网络结构等等.因此,本文提出了一种基于重叠社区搜索的传播热点选择方法,该方法通过迭代式推广模型根据用户行为反馈逐步选择影响力最大化节点,使社交网站平台在信息传播过程中充分发挥控制作用,并提出一种新型的基于重叠社区结构的方法来衡量节点影响力,根据这种衡量方式来选择传播热点.本文提出了解决该问题的两种精确算法,包括一种基本方法和一种优化方法,以及该问题的近似算法.并通过大量实验验证了精确及近似算法的效率和近似算法的准确率以及迭代式传播热点选择方法的有效性.     

动态连续时间网络表示学习

随着时间的推移,网络会随着节点和连边的变化不断发展。针对传统网络表示学习算法不能正确处理动态网络的问题,提出一种基于随机游走的动态连续时间网络表示学习算法（DCTNE）。通过定义一个灵活的节点时序邻居概念,设计一个有偏的随机游走过程。根据时间信息,有效地探索节点的不同时序邻居并建模不同邻居的影响,学习网络表示。实验证明了DCTNE动态网络时序信息的有效性。在链接预测任务上,DCTNE的AUC值与其他算法相比最高获得了50%的增益;在节点分类任务上,DCTNE相较于其他算法在效果上有明显提升。结果表明,对网络中时间依赖关系进行建模有助于后续的网络分析任务。     

基于进化谱分方法的动态社团检测

为了有效地分析动态网络中的社团结构功能和特性,在进化时间平滑框架下基于进化聚类方法对模块密度函数和否定平均关联函数进行了优化,论证了理论可行性;在此基础上提出了检测动态网络社团结构的进化谱分算法,并对两类算法进行了详细的谱分分析。分别在计算机合成的动态网络以及真实网络中检验了所提算法的准确性和有效性,并将其与其他算法进行对比。实验结果表明,所提算法对动态网络中的社团检测仍有很高的准确性和有效性。     

一种基于增广网络的快速微博社区检测算法

微博是当前最流行的在线社交媒体之一,有效地检测出微博用户的社区结构,能够帮助人们理解微博社交网络的结构和用户的行为特征,从而为用户提供个性化的服务。然而,现有社区检测算法大多只考虑社交网络节点之间的直接链接关系,忽略节点自身的内容特征。针对此问题,提出一种基于增广网络的快速微博社区检测算法。该算法通过融合社交网络的链接信息以及用户在微博上所发布的博文内容信息构建增广网络,然后以模块度为目标函数快速挖掘增广网络中的主题社区。通过真实微博社交网络的实验表明,提出的算法能够高效地检测出社交网络的主题社区。
     

基于桥系数的分裂社区检测算法研究

研究社区结构有助于揭示网络结构和功能之间的关系,而社区检测是社区结构研究的基础和核心。该文定义了一种聚集度桥系数,将其应用到社区检测中,设计出一种分裂社区检测方法,包括分裂和合并两个算法。分裂算法使用桥系数识别社区间边,通过迭代删除社区间边分解网络,从而发现网络中的社区结构;合并算法根据社区连接强度合并社区,可以揭示社区结构中的分层嵌套的现象。在六个社会网络数据集上的实验表明,本文算法可以有效的将网络分裂为有意义的社区,并且准确性接近或超过经典的社区检测算法。     

基于联合矩阵分解的动态异质网络社区发现方法

动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,本文提出了一个基于联合矩阵分解的动态异质网络社区发现方法,首先计算动态异质网路中各个快照图的拓扑相似度矩阵和多关系相似度矩阵,其次利用时序联合非负矩阵分解方法,约束各个时刻快照图的社区划分,最后在真实网络数据集上的实验结果表明,该算法可以有效检测出动态异质网络中潜在的社区结构。