基于社交网络的社团划分算法研究

硕 士 学 位 论 文 论文题目 基于社交网络的社团划分算法研究 学科专业名称 管理科学与工程 申 请 人 姓 名 马 静 指 导 教 师 马英红 教授 论文提交时间 2011 年 6 月 10 日 单位代码： 10445 学 号： 2008021254 分 类 号： 创 声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中 特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 _ (注：如没有其他需要特别声明的，本栏可空 )或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解 学校 有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权 学校 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 (保密的学位论文在解密后适用本授权书 ) 学位论文作者签名： 导师签字： 签字日期： 年 月 日 签字日期： 年 月 日山东师范大学硕士学位论文 I 目 录 摘 要 . 1 . 3 第一章 绪论 . 5 文选题的理由或意义 . 5 内外研究现状及发展趋势 . 5 要工作安排 . 7 节安排 . 8 第二章 社交网络的基本概念和社团划分经典算法 . 9 交网络的基本概念 . 9 络的表示方法 . 12 交网络的理论 基础 . 14 团结构划分算法 . 15 章小结 . 21 第三章 基于相邻节点聚类的社团划分算法 . 22 法描述 . 22 法实现 . 23 法时间复杂度分析 . 24 例分析 . 24 章小结 . 29 第四章 基于相似度的层次聚类的社团划分算法 . 30 似度的层次聚类算法 . 30 间复杂度分析 . 32 法衡量标准 . 32 验结果分析 . 34 第五章 总结和展望 . 37 作总结 . 37 一步工作展望 . 41 参考文献 . 39 致 谢 . 42 攻读硕士学位期间发表的论文 . 43山东师范大学硕士学位论文 1 摘 要 社交网络可以用来描述现实社会中的实际网络，它包括人与人之间的社会关系， 物种之间的捕食关系，科学研究中的合作关系等。大量研究已经表明在真实世界中各种不同的社交网络具有许多共同的结构特征，例如小世界性质、无标度性、社团结构等。而其中对于社团结构这一性质的研究受到了来各种学科的研究者的广泛关注，通过研究发现任一学科领域中各知识点、概念以及学科领域之间具有明显的层次关系，同一概念中的知识点、同一学科的概念等联系比较紧密，而与其它不同领域的知识联系比较稀疏。本文所研究的重点就是社团结构，它的性质可以帮助了解网络结构与分析网络特性，探测分析网络的社团结构对我们认识和理解真实复杂网络的结构 以及功能有着重要意义。目前，已经有许多研究者投身到社团结构探测的研究当中并提出了各种各样的算法以便能够快速而准确的找到网络中的社团结构，比较经典的算法如 法，谱平分法， 是划分社团的算法时间复杂度和准确性之间的矛盾仍然是大规模网络的社团结构分析面临的重要问题。在本文中，系统分析了已研究出的社团结构划分算法，比较了各几种算法的优缺点，在此基础上我们提出了两种改进的社团划分算法。 本文主要做了以下几方面的工作 : (1)研究了社交网络理论的基本知识，介绍了社交网络一些表示方法 和一些基本概念，以后寻找社团划分算法奠定了理论基础。然后又介绍了几种比较经典的算法，并总结出了它们的优点和缺点。 (2)利用相邻节点之间的距离差值构造了一种新的社团划分算法 基于相邻节点聚类的社团划分算法。首先要找到每个社团的初始聚类中心，以 M 个节点作为初始社团，计算与初节点距离最小的节点并入到相应社团中，以此类推直到网络中的所有节点都聚类到社团中，算法完成。把本文中的算法应用在网络实例上，通过检测本算法具有很高的正确率。 (3)通过计算节点之间的相似性系数判断节点之间相似度，利用相似度大的节点在同一个社团 的可能性大，相似度小的节点可能处于不同的社团来进行层次聚类。层次 聚类按 节点之 间的相似性进行分组 ，采用自底向上的策略首先将每个节点作为一个社团，然后合并这些原子社团成为越来越大的社团，用模块度 Q 来判断在算法何时停止。 本文的创新点： (1)相邻节点聚类的社团划分算法定义了相邻节点的距离差值，用这个参数定量的表示出了不同社团节点之间的差异程度。 山东师范大学硕士学位论文 2 (2)把网络中的两个节点的相似度，层次聚类算法和模块度相结合构造了一种算法，这个算法有了较高的准确率。 本论文提出的社团划分算法肯定还有许多不完善的地方，相关工作还有待 进一步研究。 关键词： 社交网络 社团结构 距离差值 相似度 层次聚类 中图分类号 ： 东师范大学硕士学位论文 3 be to in in no of is by on of us It is us to of by to of of to in as N of of is a In we of we (1) of of (2) A is by on of as it is to a (3) by is on of in to as a 东师范大学硕士学位论文 4 by . of (1) on of is of (2) of in an a of to be 5 第一章 绪论 文选题的理由或意义 社会科学各领域的研究方法近年来取得了许多明显进展，出现了上些新的研究方法或领域，社交网络研究就是其中的一个重要方面。随着以 代表的信息技术的迅猛发展，社交网络研究近一二十年已经迅速发展起来，被广泛应用到了社会学、政治学、人类学、心理学、组织管理、大众传播和社会政策研究等多个领域。社交网络研究又被称之为结构研究，从这个意义上说，社交网络研究不仅是对结构加以分析的一套技术，还是一种理论方法 结构研究的观点。即在社交网络的研究者来看，社会学所研究的对象就 是社团结构，面这种结构即表现行为者之间的关系模式。所以社交网络中的社团结构的划分也作为一个方向被拓取出来，在这一方向上产生了一些好的思想和成果，能够为以后人们的研究提供很大的帮助。 人们发现许多实际网络都具有一个共同性质，即社团结构。社团结构是一个网络概念，也就是说，整个网络是由若干个“群”构成的，节点之间的联系决定了是否在一个群落内，节点连接相对比较紧密的属于同一个群的可能 性就大。而节点之间连接稀疏的就可能属于不同的群，那么它们的联系就是群间联系。不论一个社团是以什么性质组成的一个类或模块，同一个社团内 部的节点肯定是有某些相似的特征或性质。比如在电路网络中，可以将各个节点根据其不同的性质划分为不同的社团。在大量的关于社团的研究中发现社会网络都存在社团，于社团结构的深入研究有助于分析和了解实际系统的结构和特性，可以更加有效的实现网络的设计。 由于在朋友关系网络中或社交网络中你的性别，生理特征的不同就形成的了琐的社团结构。这些分类表现在我们生活的方方面面，比如可能分成不同类型网站的万维网；代表着不同功能单位的新陈代谢网以及神经网；反映了生态系统中的子系统在网络性质和功能的食物链网 ， 综上所述社团结构的研究对于整 个人类有着举足轻重的作用，它能够揭解网络结构与分析网络特性。实际的社交系统中自动探索社团结构有非常重要的价值，实际网络中的社团结构发现能够帮助我们更加有效地研究网络。在生物学、物理学、计算机图形学和社会学中，社团结构的研究都得到了广泛的应用。 内外研究现状及发展趋势 网络社交是社交网络的起源，互联网的本质就是计算机与计算机之间的互联。电子邮件是网络社交的起点，早期的电子邮件解决了远程的邮件传输的问题，到现在为止互联网上最普及的应用仍是电子邮件。电子公告板简称 网络社交推进了一步，从理论上实现了 向所有人发布信息并讨论话题的功能把“群发”山东师范大学硕士学位论文 6 和“转发”变为一般化。 随着网络社交的进一步演进，网络上的个人特征是益趋于完整，社交网络也随之出现了。刚开始社交网络只是用来交友的，它的开 始 只是获取网络上的个人资料和好友情况。社交网络的发展过程大到经过了这样的三个阶段： 第一阶段是早期概念化阶段 ，在这段时期内 社交网络 概念 基于六度分隔理论，它是 处于被认知和等待普及阶段， 社交网络 服务单一， 是 一种降低联络成本的工具。第二阶段是资本市场高度关注 社交 网站， 社交网络 理念、经营思路、产品严重同质化 ，用建立弱关系带来更高社会资本 。第 三阶段 社交网络 用户需求呈现多样性和现实性， 它的 应用和服务在商业化方面开始超越校内网等。 社交网络的整个发展过程是遵循着人们逐渐将日常生活日趋完整的信息流转移到进行低成本管理，这样的转变使虚拟社交与现实世界之间的分歧越来越大。信息活动是人类任何活动的基本，信息活动的传递介质不同决定个体接受的信息也不同。网络社交一直在降低人们社交的时间和传递信息的成本，同时网络社交也在一直努力通过不断丰富多彩的手段和工具来替代传统社交，以满足人类日常活动交流的需求。作为社交网络起点的电子邮件时代，网络仅仅能满足人们最基本的社交 需求，那么发展到今天的社交网络已经是原来需求很多倍，大部分传统社交的作用已被现在的网络社交取而代之。目前，社交网络是一个推动互联网向现实世界无限靠近的关键力量，它包含以人类社交为核心的所有网络服务形式，社交网络使得互联网从研究部门、学校、政府、商业应用平台扩展成一个人类社会交流的工具。移动手机领域也成为了网络社交拓展的研究范围，手机的普遍性和无线网络的应用使它成为新的社交网络的载体。网络 +社交构成了社交网络，通过网络这一载体把人们连接起来，从而形成一个具有某种性质的团体。社团结构划分的研究中，划分社团主要有 两种传统算法：基于图论的算法和层次聚类算法 1 基于图论算法几乎都没有精确解，大都是一个 题。所以，当遇到规模比较大的网络时不存在精确解。然而部分试探性算法在大多数情况下可以得到较满意的结果。包括两个有名的算法： (1)法 3，它采用的是一种贪婪算法，依据使社团结构内部及社团结构之间的连边最优化对实际的网络进行分团。它是一种试探性的优化的二分算法，原理是基于贪婪算法，它的最终结果是将网络分成两个大小已知的社团结构。它的基本思想是首先给网络的划分定义一个函数 Q，定义为两 个社团内部的边的条数减去连接两个社团之间的边的条数，再寻找使函数 Q 的值达到最大的划分法。事先知道网络中的社团数目是这种算法的缺点，如果事先不知道社团数目，用这种算法的结果可能就不正确。 (2)基于 特征值的谱平分法 4谱平分法的思想是根据网络的 将其分为两个社团。它最大的缺陷是它每次只能将网络山东师范大学硕士学位论文 7 平分，如果要分成多个社团，就需要对子社团重复算法。 层次聚类算法 6于各个节点之间连接的相似性或者强度，把 网络自然地划分为各个子群。根据往网络中添加边还是从网络中移除边，该类算法又可以分为两类： (1)凝聚方法，它是以顶点为基础，通过逐步凝结形成社团。 12是基于贪婪法思想的一种凝聚算法，主要是针对结点比较多的网络。(2)分裂方法 2，它首先将网络中的所有顶点视为一个大的社团，通过逐步分割这些大社团成小社 团 。 出的 法 7一种典型的根据分裂思想得出来的，近几年已成为社团结构分的的一种标准算法，它的基本思想就是不断地从网络中移除介数最大的边。边介数是网络 中经过每条边的最短路径的条数，它为区分一个社团的内部边和连接社团之间的边提供了一种有效的度量标准。它用模块度 14为衡量的标准： i eT |)( 22 此外还有在这些典型算法上的改进，分裂方法：自包含 法 10，采用节点集的 法 11，快速分裂算法 30，基于相异性的算法 13， 基于信息中心度的算法 17。凝聚方法：利用堆结构的贪婪算法 18。还有一些两者都不属于的效果也很好的算法，比如 提出的派系过滤算法 19它是用来分析互相重叠的社团结构 21 人提出的边聚类系数法 27基于网络局部的边聚类系数思想。 以上的研究大多是国内外的学者在无权无向网络的基础上的，也就是网络中结点之间的连边没有数值的大小，用来衡量的只是边的有无，而不是边的大小。然而随着人们对社交网络中社团结构研究的深入，越来越多的发现大多现实中的网络中的边的连接是有权重的，用来衡量这个网络时不只是有没有边，还有一个因素就是边的权值的大小，因此网络中边之间权重对社团的划分产生影响，也成为值得研究的问题。针对不同类网络的特点，找到快速而且 可靠的网络社团结构分析算法仍是今后需要解决的主要问题 29。 要工作安排 社团结构是社交网络中的一个性质，通过一个实际的社交网络可以通过不同的方法来对实际网络进行社团划分，把它划分成几个不同的社团。对于社团结构的划分可以按照不同的标准来进行划分，比如年龄，性别，专业等等。本文研究了当前比较常用的社团发现算法以及应用，分析了各种算法的优缺点。本文致力于使用不同的聚类算法发现网络的社团结构。主要的研究工作如下： (1)对社交网络进行了概述，总结了社交网络的基本概念、性质、特点和应用等。 (2)提出了使 用聚类方法发现复杂网络社团结构的基本流程。 山东师范大学硕士学位论文 8 (3)提出了一个基于相邻节点聚类的社团划分算法，把网络中的相邻节点进行比较，在比较的结果中来根据距离差值的大小对相邻节点进行聚类。 (4)基丁相似度的层次聚类算法，使用常用的数据之间相似性度量方法衡量网，然后用层次聚类算法发现实际网络和已知社团结构的社团划分结果。 节安排 本文对社交网络中社团结构的分析方法方面进行了深入的研究。大量研究已经发现许多的网络化系统都是由相对独立而又相互交错的社团或块组成的。探测分析网络的社团结构对于理解网络的结构和功能有着深刻 的理论和现意义。通过了解目前寻找网络中社团结构的几种具有代表性的方法的基础上，提出了两种新的社团发现算法。在过去的几年时间里，已经有大量的社团结构算法被提出，并被用于各种真实络的社团结构探测和分析。 论文的内容安排如下： 第一章为绪论部分。这部分阐述了论文研究内容的背景、现实意义，主要包括社交网络及其发展，社交网络中的社团结构的意义以及面临的挑战。 第二章介绍了社交网络的研究，包括社交网络的发展演变，一些基本概念，主要结构特征和应用。以及一些经典的社团划分算法 ， 并对这些方法进行分析和比较，总结出它们的优点以 及缺陷。 第三 章介绍了一种新的社团结构发现算法。基于相邻节点聚类的社团划分算法，该算法对网络中的社团结构的划分具有很好的效果。与目前比较流行的社团发现算法相比较，准确率较高。但该算法只是针对于一些已经知道社团结构的网络中比较适用。 第四 章介绍了一种结合对象相似度和层次聚类算法思想的社团划分算法。对于已有的一些凝聚算法，计算的准确率上也有了很大的改善，但缺点是时间复杂度不够好。 第五 章是本文所做工作的总结，并且指出了今后研究工作的方向 。山东师范大学硕士学位论文 9 第二章 社交网络的基本概念和社团划分经典算法 社交网络不能仅仅提供人与人 之间的查找和交流工作，如果功能单一，这跟早期的交友网站没有什么本质区别。社交网络分析可以说是了解整个社交网络的工具，社交网络分析结合计算机工具可以说是决策支持系统的重大发展方向，帮助企业进行分析企业的贸易关系网和发展良恶性 ， 帮助人们对于社交网络的认识。 交网络的基本概念 交网络 社交网络的缩写， 社 交 网络是指社会个体成员之间因为互动而形成的相对稳定的关系体系 ，主要是通过一些社交关系分成的不同的类，构成的不同的社团结构 。 在网络中，博客、人 人、群落等在网络中实现了人与人之间的联系 。 社交网络是行动者之间连接而成的关系结构。一个社会网络由有限的一组或几组行动者及限定他们的关系所组成的 17。关于社交网络的划分标准不同，社交网络的类型也不同。通常，构成社交网络的主要要素包括行动者、群体、关系等。 (1)行动者：社交网络的一切个体、也称参与者。故这里的行动者不仅是指具体的个人，它是指在一个网络中与他人 (行动者 )相联结的具体的个人、组织、事件或其他集体性质的社会实体。“点”或“节点”来表示每个行动者在网络中的位置，任何一个社会单位或者社会实体都可以 看成是“点”，或者是集体性的社会单位。 (2)关系：是指群体节点之间的联系。在个体范筹上，人和人之间如果有共同的兴趣和属性或者相互认识，称之为他们之间存在着关系。在社交网络上，基于朋友关系而建立起来的网络连接，两个网络用户之间的相互信赖表示关系。一般来说，有关系的两个行动者之间拥有比其他人更多的权利，比如，有些人相互之间对对方都彼此熟悉和了解，那么他们之间的联系就会 多些。针对于对关系的双方的熟悉程度，用权值来判断双方的亲密关系 。 (3)群体：把存在关系的节点进行组合就形成了群体，群体之间的成员彼此有一些特征 是相似的，是整个网络关系的一部分。这些相似可能来自于同一个国度，同一个家乡，或者毕业于同一所学校等等。在群中能够找到和你趣味相同的朋友，有利于彼此之间对于共同感兴趣的主题的交流。 团结构定义 一是 从度的角度 ， 定义 社 团的概念是由 出的 31。如果用 示山东师范大学硕士学位论文 10 节点 i 在社团范围内的度，用 示节点 i 在社团之外的度 。 给定 n 个节点和m 条链接 N(n， m)，通过社团检测算法，获得的社团为 1c 2c .大多数的算法中，检测出的社团具有下面两个特点： 一是 ji ； 二是 包含了所有节点 。 这说明大多数算法结束的条件是，已经将所有节点都划分进了它所属的社团，并且每个节点只能属于唯一的团。总而言之，社团结构可分为强社团结构和弱社团结构两种： (1)强 社团结构 如果对任意节点 i，子网络 V 满足： ( ) ( )in k V ， 即该社团内任何一个节点与这个社团内部其他所有节点的连接，比它与该社团外部的所有节点的连接要紧密，那么称 V 为该网络的强社团结构。 (2)弱社团结构 如果子网络 V 满足： ( ) ( )in ou i k V即 社团 之间节点 的相互连接比 社 团 内 部的节点的联系更加紧密，也就是说，社团 边界 的边数之和大于社团 内部 的边数之和，那么称 V 为该网络的弱社团结构。 二是 义的社 团是一系列相连的群 32，他定义的社团有一个显著特点 :网络中可能存在的社团结构不是都那么明 显 ，很可能这些社团结构是可以重叠的，也就是说一个节点可以同时属于不同的社团结构。如果 每 个网络群中的所有节点均与本群中任意节点直接进行连接，其时就是说它构成了网络的一个完全子图，子图中的任意两个节点都有边相连，满足这个条件的就称之为群。在网络中一般把 k 群定义为含有 k 个节点的群，如果两个 k 群是相连，那么就是指这两个k 群共同享有 节点。如果对于 义的社团进行深入的研究，就会有助于我们对社交网络中的一些重叠结 构进行分析，因为社团中的某些点是同时出现在 不同的社团结构中的，所以在比较节点的相似性时，则可以推断出其他节点也具有这些特性。 社交网络中的社团结构是指同一个社团内的节点的性质与不同社团内的节点性质是有区别的，通过研究社团结构可以使得人们了解不同社团结构中的用户的性质的不同。在许多大规模的社交网络中，我们通过划分社团结构是为了了解网络中某一部分的特征，而不是整个网络 的。 “弱纽带” 指的是社团与社团之间的连接， 弱纽带使得人与人之间的距离变得非常“相近” 33，在社交网络中的作用非常强大。 均路径 长度 山东师范大学硕士学位论文 11 网络的平均路径长度是 网络拓扑结构三项最健壮的措施之一 。在朋友关系网中平均路径长度 是连接网络内两个人之间最短关系链中的朋友的平均个数 。一个含有 N 个节点和 M 条边的网络的平均路径长度可以用时间量级为 )(的广度优先搜索算法来确定。 网络的平均路径长度 L 定义为任意两个节点之间的距离的平均值 11 / 2 ( 1 ) (其中 N 表示的是网络中的节点的个数，络中节点 i 和 节点 j 之间的距离 ， 网络中两节点之间的距离是指 连接两个节点的最短路径上的边数。 节点到自身的距离为 0，而 公式 (计算两节点之间的距离时没有排除这种可能性 。 因为实际的网络节点数也是比较大的，所以公式 (差也是 可以忽略不计的 ， 不会对结果造成很大的影响。如 图 2个 网络 包含 5 个节点和 5 条边，计算可知这个网络的平均路径长度 。 通过研究发现，对于许多实际节点数规模比较大的网络来说，其时它的 平均路径长度却 非常小 。 12345图 2个简单网络平均路径长度 社交网络的研究人员利用度这个概念来分析一个节点的活跃性，度就是指一个节点同他直接关联的连线数。从上面图 2图中可以看出，节点 1 和节点 2在网络中同他关联的连线最多，说明他是网络中比较活跃的节点。它们是整个网络的连接器或者说中心点。一般性都认为在这种网络中，“中心点越多，网络越好”，但并不是总是这样，最主要的因素是看该中心点的连接整体，看其如何同其他没有直接相连的节点联系的。 山东师范大学硕士学位论文 12 络的表示方法 表示 图是关系的数学表达， 一个 实际具体的 网络可抽象 转化 为一个 图表示。图),( 代表的是一个网络，它包含两部分的内容： )( )(其中 )(网络中的节 点 集， )(表网络中的边集。 V 是 节点数记为 N ， E 是 边数记为 M 。 网络中的 每条边 与网络中的节点都是 相 互 对应 的 。 网络大致可分为以下几类： (1)无向网络 ， 任意点对 ),( ),( 应同一条边 。 (2)有向网络 ，节点对 ),( ),( 属于同 一条边。 (3)加权网络 ，网络中的 每条边都赋予相应的权值 。 (4)否则称未加权网络，网络中的边的不给予赋值，在网络中的重要性都是一样的，也就是我们常用的每条边的权值都为 1 的等权网络。 图 2出了几个 常见的网络的 例子。 一般来说我们所指的网络都 指无向 等权 网络 ，而且不存在这样的两种情况 (1)任意两个节点不可能有多条边进行连接，即无重边。 (2)同一个节点之间不能有边连接 ，即无自环，而符合这两种情况的网络称为单图。 图2示了四种不同的网络， (a)单一类型节点和边的无向网络 ， (b)不同类型节点和边的无向网络 ， (c)节点和边权重变化的无向网络 ， (d)有向网络 。 图 2同类型网络的例子 阵表示 (一 )邻接矩阵 邻接矩阵是指矩阵中的元素ji,i 到节点 j 的边的条数。具体来说，有 n 个节点的图 G 的邻接矩阵 )(一个 矩阵，其中若 接么山东师范大学硕士学位论文 13 1否则 0因此，有 n 个点的简单图与对角线元素为零的 n 阶 对称二元矩阵之间是一一对应关系，其中的元素取值为 0 和 1。如图 2网络关系，用邻接矩阵表示为： A0000100010000110110110110。 (二 )关联矩阵 关联矩阵是关于图 G 的点和边 的矩阵，记作 )(具体来说，对于一个图，指的是一个 0， 1 矩阵，其中 i ， j 元素取 1 当且仅当节点 i 与边 j 关联。对于有向图，如果节点 i 是边 j 的头部，则矩阵 i ， j 取 1，如果节点 i 是边 j 的尾部，则矩阵 i ， j 取 1，其他情形取 0。在一般情况下，指的是表示隶属关系的矩阵，因此它可能是方阵，也可能不是，例如图 2关联矩阵为： 图 2三 )距离矩阵 距离矩阵是根据节点间的距离形成的矩阵，对一个 n 个元素的图 G ，)( ., 21 ，定义 的距离矩阵 D 满足 ( , )ij i jd d n n 。对于.,21， ，有 0而且因距离函数是关于距离的，满足 )( ji )( ij ，因此 ij 。由此得到 D 为对称矩阵。例如图 2其距离矩阵为：1 0 0 0 1 1 11 1 0 0 0 0 00 1 1 0 0 1 00 0 1 1 0 0 10 0 0 1 1 0 0R 山东师范大学硕士学位论文 14 332123112131121211121221121121D。 图 2交 网络的理论基础 桥问题 在 1736 年，当时欧拉发表了一篇论文，给出了一个一般性的理论，其中包括现在被称为七桥问题的解。其背景是一个非常有趣的问题：在 郊的 上有两个小岛，小岛和河两岸的陆地由 7 座桥相连 ， 如图 2-5(a)，问题是如何从河岸或岛上的某一个位置出发，能经过 7 座桥正好各一次，最后回到出发地。有人尝试了很多次，始终没能成功。 图 2-5(a) 图 2-5(b) 论文中，给出了该问题的数学模型，用 4 个点代表 4 个被河隔开的陆地 (两岸和岛屿 )，把桥表示为连接两个陆地之间的边，则得到图 2-5(b)所示的图，从而问题变为如何从图中的某个点出发，经过所有的边正好一次，最后回到这个点。在研究这个图的基础上， 论文中证明了该七桥问题无解，并且给出了一些规律性的理论。把实际问题抽象成点和边构成的图进行研究。 度分隔 存在小世界现象是被六度分隔理论证明的。六度分隔理 论的早出现是在 20世纪 60 年被美国的著名社会心理学家米尔格伦提出来的。“你和世界上任何一个陌生人之间所间隔的人不会超过六个，其时也就是最多通过六个人你就能够认识世界上任何一个陌生人。” 为了研究连接人与社区的人际关系网，一位哈佛大学的心理学教授斯坦利 米尔格拉姆在 1967 年做了一次信件传递实验，发现了山东师范大学硕士学位论文 15 “ 六度分隔 ” 现象。这一现象可简单地概括为：你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。简单地说：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，如果你想认识一个陌生人最多通过六个人你就可以完成。” “弱纽带”问题是社会人际关系中普遍存在的现象，而六度分隔理论正好说明了这种存在，弱纽带在社交网络中的作用是非常强大的。通过弱纽带人与人之间的距离变得非常“相近”，这种效果在找工作或者是处理事情时就会体会到。研究社交网络中的弱纽带问题，并把它变成了一个可以进行评估的数学模型，后来发表在自己的论文“ 。交往中可能大家有共同认识的人，所以我们经常与新结交的朋友说的一句话是“这个世界真小”曾经“六度分隔 ”理论只能作为理论而存在。但是，互联网的产生与发展使一切成为现实。互联网的发展促进了六度分隔理论的发展，从而使得各种应用软件越来越趋向于人性化、社会化，实现了人的活动与软件的功能融为一体，也就是说这些软件对于真实的社交网络中的人际关系的发展和交往活动起来反映和促进的作用。应用软件所构建的“弱连接”，在人们的日常生活中扮演着越来越重要的角色，这是六度分隔理论的进一步发展的趋势。 团结构划分算法 首先来介绍进行社团结构划分的其中一类算法 是一种传统的算法。网络中的社团结构的划分是根据互相 连接的节点之间相似性或者强度实现的。凝聚方法和分裂方法是聚类算法中的两大类，凝聚方法是在网络中进行加添边操作，而分裂方法从网络中移除边来实现社团划分。 节点对之间的相似性是凝聚方法的基本思想，添边的过程如下：首先假设一个网络的初始状态是有 N 个节点，零条边；然后通过一定的方法来计算相连的节点之间的相似性；再按照计算得出的相似程度在具有 N 个节点， 0 条边的初始网络中添加边。根据需要在任何一步都可以终止操作。不论是在哪一步操作终止，停止下来的网络的状态就是由不同的社团结构组成的。树状图表示 从初始网络到最终形成的网络 算法的流程。最底层代表网络的最初状态， 包含 N 个节点，但是没有边连接。随着层次的增加，各节点也逐步凝聚成更大的社团。当所有的点都经过直接或间接相连时，就构成了一个社团。在每一层切断连线都能形成一种社团结构。 法 1 算法的基本思想 法是一种基于贪婪法原理的算法，在试探进行时逐步优化实现的。首先引进 Q， Q 是一个函数表示的是两个社团内部的边数之和减去连接两山东师范大学硕士学位论文 16 个社团之间的边数。然后实行 法，使 Q 值达到最大。 2算法的实现 整个算法用下面的步骤进行 描述： 步骤 1，将网络中的节点随机的划分为两个大小已知的社团 。 步骤 2，对分别来自两个社团的所有可能的节点对进行琢磨，然后交换这两个属于不同社团结构的两个节点，计算交换这两个节点后得到的 Q 值，比较所有属于不同社团的两个节点得到使 Q 值最大的节点对，并把对应的节点对进行互换，但是值的注意的是不能多次交换节点，一个节点只允许被交换一次。与此同时记录交换以后的 Q 值。 步骤 3，重复步骤 2，当网络中的所有节点都被交换过，算法停止。 经过算法在实际网络上的应用发现， Q 值在节点的交换过程中并不一定是单调递增的，但很可能在之 后步骤中出现一个最大的 Q 值，虽然在之前的过程中交换节点对时使 Q 值有所下降， Q 最大值对应的社团结构就是最终的结果。 虽然 法得到的结果正确率是很高的，但是它的前提是已知网络划分为两个大小已知的社团，不然就不能得到正确的结果，这是法的缺陷。 平分法 1 阵 一个 n 个节点的无向图 G 的 阵是一个 维的对称矩阵，记为 )( ， 其中对角线 节点 i 的度，非对角线 节点 i 和节点 j 之间有边相连，否则，当节点 i 和节点 j 之间无边相连 。 K 是一个对角矩阵，对角线上的元素为对应的各个节点的度， A 为该网络的邻接矩阵， 阵 L 也可以表示为 。矩阵总有一个特