基于图挖掘的网络社团结构发现

发布时间：2020-09-29 17:03

　　 现实世界的网络里自然地包含了很多社团结构,它们已经成为网络系统中一个重要的统计特征。例如,在社会网络中,它们可能代表着一组俱乐部成员;生物网络里,或许是一组功能相关的基因组;在语意网络中,它们是一些与某个主题相关的网页。通常来讲,社团结构是一些联系紧密的实体,结构内部节点之间的联系相对网络中其它节点更紧密。如何高效地挖掘出这些结构对理解和分析网络结构来说是一个很重要的问题。 尽管在网络社团的发现方面已经取得不少研究成果,但仍然存在许多问题有待解决。比如,有些算法的效率不是很高,社团结构的度量机制不够完善;很少有工作去关注重叠的社团结构,虽然重叠的结构在现实的网络中更普遍存在,也更能反映出真实世界的本质。针对这些问题,本文借助一些经典的算法来产生社团结构的种子,然后以拓展种子的方式来挖掘网络中重叠和非重叠的社团结构。本文的主要贡献如下: 1.结合多层次策略,文中运用经典的图谱划分方法产生了种子集合,并对种子的特征进行了分析。多层次策略使得算法在计算最粗糙图的Fiedler向量时具有很好的划分速度;谱平分方法帮助算法过程找到很好的图划分线索。这些种子集合抓住了社团结构的主体,反映出了目标社团的特征,具有很好的性能。 在真实的网络数据上,文中也对种子选取的合理性做出了验证。 2.运用种子拓展的方式提出了一种新颖的社团识别算法。该算法基于模块函数和节点的传递概率。模块函数是由Newman和Cirvan来定义的,它已经成为度量社团结构的一种主流标准。算法用它的改变值来评估新扩展节点对当前种子集合的贡献。传递概率在算法中被用来推断相邻节点之间的联系,反映扩展到新节点的权重。传递概率的源头是种子集合中节点的初始概率(初始权重)。新节点得到的概率决定了计算节点贡献值的次序,贡献值又决定了节点是否具有进一步扩展的机会。第4章对算法过程做出了详细的描述,同时也对扩展过程中节点的删除操作和扩展步上逃逸的概率做出了分析。 3.对网络中普遍存在的而又很少被关注的重叠社团结构,文中提出一种识别算法。对解决重叠问题,它开辟了一条新的途径。该算法仍然基于种子扩展。在得到种子集合之后,算法结合随机行走技术给出了一种合理的扩展过程,它用时间步来刻化。在扩展的每个时间步,算法首先计算出所有标准化后的节点概率。按照概率值的降序,所有的节点依次被扫描。然后,确定哪些节点在接下来的时间步里作进一步的扩展。通过节点扫描,算法还要对新扩展的节点作出是否为当前的种子集合贡献者的判断。这些判断主要用于寻找候选社团在当前时间步最优的结构。运用贡献节点的性质,文中给出了一些定理。基于性质定理,一些无用的扩展节点在寻找候选社团的最优结构时可以被安全地删除。扩展过程执行上述步骤直到社团结构之间的重叠率超过了用户的忍受范围或者到达了随机扩展的收敛时间。 第5章不仅介绍了算法步骤,也对扩展过程给出了理论分析。分析表明,提出的方法使得候选社团在每个时间步上都能找到最优的结构,基于懒惰随机行走的整个扩展过程也能给种子集合带来好的扩展结构。 4.在六个网络数据集上,对上述提出的算法作出了验证。数据集来自真实的网络,规模大小不等,内容涉及多个领域。在实验分析上,文中从多个角度运用多种机制来评估算法。评估内容包括种子选取方式上的对比,算法与相关工作的比较以及时间分析等。对重叠的社团结构,还给出了在著名的网络里发现的实例。实验结果表明文中提出的方法具有一定的优越性,同时也证明了重叠方式对识别完善的社团结构是非常重要的,让大家认识到重叠社团在真实网络中的研究意义。 综上所述,本文针对网络中的社团发现问题提出了几种新算法。这些算法采用了种子扩展的方式,扩展过程基于随机行走技术,扩展结构选用了模块函数来度量。文中用理论分析和大量的实验验证了这些算法。结果表明提出的方法能识别出结构完善的社团结构,具有很好的性能。
【学位单位】：复旦大学
【学位级别】：博士
【学位年份】：2008
【中图分类】：N941.4
【部分图文】：

网络系统的概念已被引入到多个领域{1。2，3，4，5，6，7}，如社会网络【8，9}、万维网[10， 1112，14，15」、生物网络【16，33」、经济学网络{18，19}、科研合作网络{2。」、世界的航空运输网络【39」、食物网络【36，37}等等。图1.1到图1.4展示了其中几种网络实例。这些复杂的网络，是重要的信息资源载体，包含着丰富的内容，并且内容之间的关系也极其错综复杂。面对如此庞大繁琐的网络，人们迫切需要挖掘海量数据中隐藏的有用信息。网络图中包含着什么特征?网络元素之间的复杂关联又蕴含着什么意义?如何从这些网络图里快速有效地挖掘出有意义的信息?解决这些问题对理解网络结构和分析网络特性具有很大的帮助。网络元素可作为图中的节点，元素之间的联系作为图的边。用图的节点和边来存储一些附加信息，以图的方式!咧对网络建模。这样就可以借助图挖掘的方式来分析网络中有趣的元素和数据元素之间的关联。社团结构是网络图中呈现出的一个重要特征一一每个社团内部节点之间的联系相对图中其它节点更紧密「 2125)。这些节点通常是图中具有相同属性或者扮演相似角色的一组集合，所以社团又被称为类，模块，粘在一起的子图。图1.5和图1.6展示了两个实例，它们分别代表了非重叠和重叠的社团结构。在网络中识别或发现这些社团结构具有重要的实用价值。属于同一个紧密相连社团中的节点更加可能在其它方面上具有相同或相近的性质。如社会网络中的社团可能是根据共同兴趣或背景而形成的社会团体;万维网里，社团结构或许代表着有与某个共同主题相关的网页!10

某个工作组内elllail通信构成的网络

图1.1:与某个站点相关的网页书今.二二袅翻..-.二一.臼份:，.侣今.，.::..…::铭不令...……图1.2:某个工作组内elllail通信构成的网络尹

【引证文献】

相关硕士学位论文 前3条

1 刘微;复杂网络中社团结构的发现[D];辽宁师范大学;2011年

2 彭玲;基于主题及核心人物的邮件网络社区发现研究[D];苏州大学;2010年

3 许冲冲;基于偶图分解的电压控制区域划分[D];华北电力大学;2012年

本文编号：2830012