论文部分内容阅读
现实世界中大量复杂系统可以抽象为复杂网络模型,社团结构是复杂网络的关键结构特征,网络的整体功能是网络中各社团相互作用的结果。因此社团结构检测是复杂网络研究中的重要内容。本文研究复杂网络社团检测算法及其在生物领域和社会领域的应用,主要包括以下几点:1.在很多真实网络中,由于一个顶点需要行使不同的功能,该顶点可能同时属于多个社团,这导致社团间存在一定程度的重叠,为了检测重叠社团结构,对近邻传播算法(AP)进行改进,提出一个重叠社团检测算法OAP。AP算法检测社团结构时,先识别出所有社团的中心点,再为每个顶点唯一指派一个中心点,拥有相同中心点的顶点集合就构成了一个社团。在中心点指派时,有时会出现顶点在多个中心点间难以选择的情况,AP通过扰动网络避免这种情况发生,而该现象可以作为识别重叠点、设计OAP算法的重要依据。OAP先用AP对网络硬划分,再利用AP的上述特点识别重叠点的候选集,最后将候选集里那些会使社团变稀疏的顶点作为噪声过滤掉,即得到重叠社团结构。实验利用空手道网络验证了候选集选择策略的合理性,利用蛋白质相互作用网络验证了算法能够更准确的检测社团结构,并且检测到的社团更有意义。实验结果说明OAP算法是一个有效的重叠社团检测算法。2.除了拓扑结构,网络中的顶点还具有属性信息,为了检测拓扑结构稠密且属性信息相似的社团,提出一个基于顶点特征的社团检测算法。首先定义顶点间基于特征子空间的特征相似性,然后结合顶点特征相似性和拓扑相似性,计算网络中边的相似性,接着利用单链接分层凝聚算法对边聚类,最后提取边上的公共特征作为社团特征。实验利用Facebook网络数据验证了算法能够快速准确的检测出社团结构,并能很好的解释社团含义。利用酵母PPI数据说明算法能够准确检测到具有生物意义的社团,并给出该社团可能行使功能的时间。实验结果说明算法具有普适性,能够在顶点具有属性信息的网络中识别有意义的社团结构。3.分析动态网络不同时刻间社团结构的变化以研究网络演化规律与特点是动态网络研究的重点。由于动态网络相邻采样时刻网络结构一般变化不大,为避免对相似网络重复聚类,提出一个基于桥系数的静态局部社团检测算法和在此基础上的增量社团检测算法。首先利用静态算法提取每个社团的最小桥系数生成树,最小桥系数生成树的导出子图就是t1时刻的社团结构,然后通过桥系数的变化判断t时刻可能出现结构变化的社团,最后局部调整这些社团,以得到符合t时刻网络拓扑的社团结构。实验利用足球队网络数据验证了静态局部社团检测算法的精确性,利用构造数据验证了增量算法的精确性,利用DBLP数据验证了增量算法的高效性。实验结果说明算法能够利用前一时刻的社团结构和增量信息,快速准确的检测当前时刻的社团结构。4.蛋白质复合体预测对理解生物体结构与功能之间的关系具有极其重要的意义。研究发现蛋白质复合体由一个核和一些附属蛋白质构成,对复合体的拓扑结构目前没有明确的定义,本文从边的角度刻画复合体的核结构,提出一个基于边的蛋白质复合体检测算法。算法首先识别出所有的核边,然后对核边聚类得到候选核,接下来过滤候选核以保证其中不存在重叠程度较高的核,最后检测每个核的附属蛋白质,得到蛋白质复合体。实验利用DIP数据库中的酵母PPI和文献中的Gavin PPI数据,验证了算法的精确性。实验结果说明算法能够更准确的检测蛋白质复合体,识别出位置一致性和语义相似性都更高的复合体。5.作为沟通和分享信息的平台,在线社交网络已是人们生活中必不可少的一部分,为注册用户推荐朋友是社交网站必须提供的重要服务,为了解决这个问题,提出基于社交圈的朋友推荐算法。算法基于有相似社交圈的用户更易成为朋友的假设,定义了用户间的社交圈相似性,然后将社交圈相似程度大的间接邻居作为潜在好友推荐给用户。实验使用YouTube数据验证算法假设;使用Facebook数据验证朋友推荐算法的准确性。实验结果说明算法能够更准确的预测好友关系。