复杂网络中的社团发现与链路预测

发布时间：2020-11-11 08:45

　　 社团结构是复杂网络的重要特征之一,可以用来表达网络的一些功能和特征;链路预测用已知网络拓扑结构特征和节点属性预测两个节点之间产生连边的概率,两者对复杂系统的研究和应用都具有重要的理论和现实意义。为了降低标签传播算法在社团发现中由于随机性引发的聚类结果不稳定的问题,使用社团归属度来确定社团个数和社团初始形状,很大程度上改进了标签传播的随机选择缺点。提出的LPA-CBD(Label Propagation Algorithm Based on Community Belonging Degree,基于社团归属度的标签传播算法)算法首先寻找平均吸引力最大节点的初始社团,然后通过社团归属度来优化或扩大初始社团,在得到网络的初始社团划分后,对剩余节点利用标签传播算法进行标签选择。实验通过在十个真实网络以及3个人工网络上测试,并与经典的LPA、随机游走算法、BGLL算法、GN算法、快速贪心算法、Leading Eigenvector等社团发现算法在社团数量、算法准确度和模块度等评价指标上对比,实验证明LPA-CBD算法在各个指标上表现良好,不仅具有较低的算法复杂度和较高的社团发现质量,并且提高了原始标签传播算法的稳定性。社团结构是网络中普遍存在的拓扑特征之一,许多真实网络的社团结构不但具有层次性,还具有重叠性,目前大多数工作只研究网络的层次性和重叠性的一个方面。Ahn在2010年发表的文章证明了层次性和重叠性是网络社团结构相同现象的两个方面,本文在Ahn的方法的基础上提出了社团检测的新算法:SAoLG(Spectral Analsis of Line Graph,线图的谱分析),将谱分析方法应用到边社团发现上,进行了兼顾层次性和重叠性的社团检测研究,实验中使用的网络有一个标准网络、两个社团结构清晰的网络(空手道俱乐部网络和海豚社交网络)以及四个真实网络,实验结果的评价准则选择模块度modularity、划分密度PD(Partition Density)、社团数目CN(Community Number)、节点覆盖率CR(Coverage Rate)、未覆盖节点数UV(Uncovered Vertices)、节点划分准确率Accuracy、正确划分节点数CDV(Correctly Divided Vertices),实验对比算法分别为Ahn的算法(LC算法)、CPM算法和GN算法,实验结果表明SAoLG算法实现了网络的重叠社团检测并且社团划分的结果优于其他三个经典的社团检测算法。网络的社团结构同样影响着复杂网络链路预测的准确性。利用图的拉普拉斯矩阵的特征向量作为样本空间进行社团结构划分能够收敛到全局最优,是很好的划分社团结构的方法之一。通过引入基于拉普拉斯矩阵的相似度计算方法,提出一种链路预测新算法:LPbSA(Link Prediction based on Spectral Analysis,基于谱分析的链路预测),将对节点提取属性特征进行边的预测转化为直接对边提取属性特征并根据其属性值进行预测。LPbSA算法首先获取网络拉普拉斯矩阵的特征值和特征向量,选择最小非平凡特征向量的维数为2维和3维,分别获取2维和3维最小非平凡特征向量对应的相似度(文中使用角距离、欧式距离以及曼哈顿距离三种相似度),得到网络中所有节点对之间可能存在的边的6个属性,然后使用机器学习算法对边进行分类,分类变量的值为0和1,其中0表示节点对之间无连边,1表示节点对之间有连边,这样就将网络的链路预测问题转换成了对边的分类预测问题,实验在七个真实数据集上分别与基于节点局部信息的相似性指标、基于路径的相似性指标和基于随机游走的相似性指标三类算法共18个相似性指标的链路预测结果作对比,实验结果证明了LPbSA算法的可行性、有效性。
【学位单位】：兰州大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：O157.5
【部分图文】：

实现对客户群的细分，从而推出不同的消费套餐及潜在流失用户的挽留方法；在生物领域，通过对生物网络的社团划分来对基因进行分类，方便科学家研究基因组包含的遗传信息和相互关系，从而为预防和治疗许多疾病提供科学依据；在电子商务领域，通过对电子商务网络的社团划分帮助电子商务用户寻找具有相似浏览、相似购买行为的客户，实现精准的推荐服务。所有这些应用，都涉及到对事物或实体的分类问题，可以说分类是人类解决真实世界问题的基本方法之一。现实生活中的复杂系统元素数目很多，元素与元素之间往往存在强烈的耦合作用，可以将这些复杂系统描述为复杂网络，通过复杂网络的理论方法研究复杂系统成为目前科学界研究的一个热点。社团结构是复杂网络的一个显著特征，网络中的社团与社团之间往往不是绝对分离、没有任何关联的，具有重叠性的社团检测的研究更接近于真实网络的构成。不同于传统的定义，社团是节点的划分，边社团把社团定义成一系列边的集合，这样节点可能拥有几条边，这些边又属于几个社团，因此这个节点可能属于两个或更多的社团。本论文主要研究了复杂网络中的社团检测以及社团结构对链路预测影响的相关问题，图 1-1 是一个航空网络示意图，该图中节点和连边错综复杂，是一个典型的复杂系统。

图 1-2 复杂网络小世界特性，六度分割理论（图片源自：tp://blog.csdn.net/zdy0_2004/article/details/50388376）小世界特性经常用两个特征来衡量，特征路径长度(C聚集系数(Clustering Coefficient)。路径长度是指连通网络连边数，网络中所有节点之间的路径长度的平均值就是网集系数假设一个节点连接着 条边，那么这 条边连接的节边数为 ( ) ，实际存在的边数和最多可能存在边数集系数。所有节点的聚集系数的平均值就是网络的聚集聚集系数反映相邻两个人之间朋友圈的重合度。标度特性(Scale-free)。现实世界中的网络大多不是随机网点拥有很大的度，而其他大部分节点的度很小的情况，也幂律分布，这就是网络的无标度特性，研究中把符合幂律网络，图 1-3 是一个拥有 10 万个节点的无标度网络的度映了复杂网络的异质性，各节点之间的度数具有严重的

1-3 拥有 10 万个节点的无标度网络示意图（引自网站//blog.csdn.net/zdy0_2004/article/details/50388376结构特性。图 1-4 是网络社团结构特性的一种描述，分”中就有社团划分的含义，现实世界中复杂网络的如各种朋友圈、同事圈、亲人圈、同学圈等，这种集的程度。复杂网络的社团检测是本论文的重点研究
【参考文献】

相关期刊论文 前7条

1 许进;杨扬;蒋飞;金舒原;;社交网络结构特性分析及建模研究进展[J];中国科学院院刊;2015年02期

2 雷方元;蔡君;;基于社团特性的链路预测算法的研究[J];广东技术师范学院学报;2015年02期

3 傅颖斌;陈羽中;;基于链路预测的微博用户关系分析[J];计算机科学;2014年02期

4 张俊丽;常艳丽;师文;;标签传播算法理论及其应用研究综述[J];计算机应用研究;2013年01期

5 吕琳媛;;复杂网络链路预测[J];电子科技大学学报;2010年05期

6 张明科;陈政;于长军;朱荣花;权太范;;网络化战争中的复杂网络拓扑建模[J];航天控制;2007年04期

7 李一宁;汪小帆;;复杂网络上的一种映射网络模型[J];系统仿真学报;2007年11期

本文编号：2878991