《复杂网络社区发现及其动态演化研究》由会员分享，可在线阅读，更多相关《复杂网络社区发现及其动态演化研究（88页珍藏版）》请在金锄头文库上搜索。
1、太原理工大学 硕士学位论文 复杂网络社区发现及其动态演化研究 姓名：苏卫华 申请学位级别：硕士 专业： 指导教师：王莉 太原理工大学硕士研究生学位论文 I 复杂网络社区发现及其动态演化研究 摘 要 复杂网络社区发现及其动态演化研究对于现实生活具有非常重要的研 究价值，它引起了许多领域研究者的关注。本文提出了三个复杂网络社区 研究的算法， 第一个算法是改进后的多社区谱分解法，后两个算法引入“线 图”来进行社区研究。 针对传统的谱分解存在网络平分或者递归平分问题，提出一种基于点 的分步骤的复杂网络谱分解的多社区算法(NSDA)。首先，该算法利用先验 信息对复杂网络中的特殊结点和局部特殊结构进行预处
2、理；接着，建立 Laplace 矩阵，对该矩阵进行谱分解，从而得到三个特定的特征值及其对应 的特征向量，以三个特征向量的元素为坐标形成直角坐标系下的结点分布 图；最后，通过坐标系中的结点分布图确定阈值，根据阈值来确定相应社 区成员，从而构造出多个社区。 本文用“线图”来改进 NSDA 算法，运用线图优势，提出了一种基于 边的有覆盖的多社区的探测方法(ESDA)进行多社区发现。该算法有三个步 骤：第一，复杂网络原始图转换成线图；第二，用一种基于点的分步骤的 复杂网络谱分解的多社区算法（NSDA）来划分社区，近而得到线图的社区 划分；第三，再把线图的社区划分转换为原始网络结构，得到有覆盖的社 区划
3、分，从而确定社区成员。 太原理工大学硕士研究生学位论文 II 本文再次把线图应用到社区动态演化研究，提出了一种基于线图的启 发式的分层聚合的社区动态演化方法。该方法主要分为四步：首先，对一 定比例的、低语义相似度的结点进行预处理；其次，对复杂网络的历史权 值和瞬间权值按比例进行计算得到综合带权网络图；把综合的带权网络图 转换成线图。再者，以一定比例的语义相似度高的节点为中心进行聚合， 再把处理后的结点进行分层，确定社区成员。最后，依据模块度公式进行 计算，合并能提高模块度的社区，寻找相对较佳的社区划分。 关键字：线图，多社区，覆盖，动态演化，有权模块度 太原理工大学硕士研究生学位论文 III
4、RESEARCH ON COMMUNITY IDENTIFICATION AND DYNAMIC EVOLUTION IN COMPLEX NETWORKS ABSTRACT Community identification and dynamic evolution in complex networks, which exist in many different fields of study, have been playing a more and more important role in peoples everyday life. This dissertation pres
5、ents three algorithms to detect community structure in complex networks, the first algorithm improves traditional spectral decomposition method, and the two algorithms take full advantage of line graph to find community. Traditional spectral decomposition algorithm performs a bisection of the networ
6、ks. Partitions into more than two clusters are usually attained by iterative bisectioning. we present a node-based spectral decomposition algorithm (NSDA) to find multi-community. There are three steps in NSDA：Firstly, some special nodes and local gathered structures are pre-processed. Secondly, we
7、establish Laplace matrix and utilize three eigenvectors that are corresponding to the three special eigenvalues to obtain the graph of node distribution in a 3-dimensional coordinate system. Thirdly, we determine threshold of community structure in a 3-dimensional coordinate system, to find the memb
8、ers of the community. 太原理工大学硕士研究生学位论文 IV This dissertation presents an improved NSDA, which refer to Edge-based Spectral Decomposition Algorithm (ESDA). It takes advantage of line graph to find overlapping community. ESDA of community follows the three steps: firstly, the ESDA transform from origin
9、graph to line graph. Secondly, ESDA apply NSDA to obtain community division of line graph.Thirdly, we transform from community division of line graph to community division of original networks to achieve overlapping community and determine members of the community. Line graph again is applied to dyn
10、amic evolution of community; we put forward a heuristic hierarchy and aggregation algorithm of line graph.The method has four steps: firstly, these nodes with low semantic similarity want to be pretreated in an original complex networks. Secondly, historical value and temporal value of networks are
11、calculated with factor to obtain integrated graph of weighted networks, then it is converted into line graph of weighted networks. Thirdly, a certain proportion of nodes with high semantic similarity are polymerized with its closest friend nodes, and then all nodes are stratified, to achieve the mem
12、bers of community. Fourthly, more importantly, the method gradually merges some communities into higher-level ones as compared to the corresponding weighted modularity, to find a potentially better exploitation of the structural community of complex networks. KEY WORDS: line graph, multi-community,
13、overlapping, dynamic evolution， weighted modularity 太原理工大学硕士研究生学位论文 1 第一章 绪论 1.1 社区研究的背景及意义 18 世纪，Eular 提出并解决了著名的“七桥问题”问题，由此开始的图形理论在随 后的几个世纪里慢慢发展起来，因此该问题也是用图论描述复杂网络的一次尝试。图论 的发展，为复杂网络的研究提供了有力的理论支持和研究工具。直到上世纪 60 年代， 两位数学家创立了随机图理论。此后的几十年来，随机图理论一直是研究复杂网络结构 的基本理论，E-R 随机网络模型由此一直成为研究复杂网络的基本模型。但是，事实上 绝大多数复杂
14、网络结构并不是完全随机的。 世纪之交，复杂网络研究人员冲破了传统图论理论，特别是随机图理论的束缚，以 小世界网络和无尺度网络重要发现为标志，从而复杂网络的研究取得了突破性进展。此 后，复杂网络的研究迅速发展，渗入到很多学科领域，并不断与这些学科、领域相互交 叉、相互促进，取得了丰硕的成果。另一方面，由于计算机技术的发展，拓宽了复杂网 络研究对象的范围。随着相关理论出现了重大突破、研究领域迅速拓展、研究内容的不 断深入和研究手段与方法的不断创新，开创了复杂网络研究的新纪元1,2。 复杂网络(Complex Networks)是由规模巨大的节点和链接关系错综复杂的边而构成 的网络结构。 其中节点本
15、身像个智能体， 具有主体性与能动性， 节点间构成的网络结构、 网络的形成与演化过程都充满了复杂性，是一个非常形象的概念。 复杂网络中存在多种性质、不同类型的节点以及丰富的关系结构，一般把连接关系 稠密的节点及其连接关系构成的子网络结构称为 “社区3” ， 即社区内的连接关系呈稠密 结构（社区内的边数多） ，社区间的连接关系呈现稀疏结构（社区间的边数少） 。这些节 点的相互作用和它们之间的关系变化，引起了社区的动态演化。 人类生存、生活应用环境中存在着大量复杂系统大都可以用复杂网络加以描述，并 且这种大量的复杂系统也都是动态变化的。例如，社会网：演员合作网，友谊网，姻亲 关系网，科研合作网，Em
16、ail 网；生物网：食物链网，神经网，新陈代谢网，蛋白质网， 基因网络；信息网络：WWW，专利使用网络，科学家合著网络（如图 1-1） ，计算机共 享网络；技术网络：电力网，INTERNET（如图 1-2） ，电话线路网；交通运输网：航线 网，铁路网，公路网，自然河流网。 太原理工大学硕士研究生学位论文 2 图 1-1 科学家合著网 Fig.1-1 scientist coauthor network 图 1-2 因特网虚拟展示 Fig.1-2 Internet virtual exhibition 太原理工大学硕士研究生学位论文 3 在计算机为媒介的技术协作网络、产品制造网络、知识创新网络中，一般存在两种 社区模式，一种是较为稳定的社区，它一般是物理世界或真实世界的社会组织结构所决 定的。例如，某一研究机构，某一研究团队，某一组织机构内人员之间 Email、即时通 信等很
