复杂网络中基于已知分组的社团探测方法

发布时间：2018-03-08 12:07

本文选题：复杂网络　切入点：社团结构　出处：《中国科学技术大学》2017年博士论文　论文类型：学位论文

【摘要】：在我们周围,复杂系统是普遍存在的。为了研究复杂系统,人们作了各种努力,建立了多种理论,而复杂网络是二十世纪末开始兴起的其中一种尝试。复杂网络是对复杂系统的一种抽象,这种抽象抓住了复杂系统的两个要点:个体与相互作用。这样做有以下三个好处:能将系统简化、降低系统的复杂度及维度;使得系统能用图论的数学语言描述,提供了一个直观的图像;为各种不同系统的研究提供了统一的框架。复杂网络虽然是复杂系统的一种简化,但仍然很复杂,这就需要我们将维度进一步降低,从不同的侧面去观察网络。从不同的角度去观察和刻画复杂网络,能发现网络不同方面的特性,例如无标度特性、小世界特性等。而本文的研究重点,社团结构,是从大标度结构的角度刻画复杂网络。社团结构是复杂网络的一种重要结构,本文对其重要性进行了总结,包括:社团结构有助于我们理解复杂网络的组织原理,社团结构在大量的真实网络中涌现,社团结构是连接网络结构与功能的一座桥梁,社团结构对网络其它结构的识别具有一定的作用,社团结构对网络的动力学行为有显著影响,社团结构提供一个观察网络的特定标度的视角,社团结构为一些算法提供一个验证的平台。但是,对很多真实网络,我们往往只知道拓扑结构,而社团结构是未知的,这就需要我们对社团结构进行探测。为了进行社团结构探测,人们建立了多种方法,本文主要介绍了基于模块度的方法和统计推断方法两种。为了比较这些算法的性能,需要进行检测,通常是在具有参考分组的人工基准网络和真实网络中进行。在真实网络中,参考分组为领域专家基于网络的附加信息所给出,并且能被多种探测算法所恢复,这样的分组称为专家分组,往往被默认代表着网络的真实的社团结构,要求算法能将其恢复。尽管专家分组广泛使用于社团探测算法的检测,但很少有工作关注于专家分组本身的评估。本文提出关于社团结构与专家分组之间关系的一个新的概念:完备性,即已知划分(不管是专家分组还是来自于社团探测算法)是否包含着网络社团结构的完整信息。为了研究这一问题,定义了一个关于社团结构的新的评价指标:排除模块度,并基于统计物理的空穴理论,建立一种具有数学原理的方法。本文发现,对空手道俱乐部网络,专家分组包含着网络社团结构的足够信息。而对于著名的政治博客网络,出人意料地,专家分组对社团结构的表达并不完备,说明还有隐藏在专家分组背后的未知结构,意味着社团结构与专家分组的关系需要重新检查。作为副产物,本文建立的方法还能用于探测隐藏的社团结构,在不删边的情况下发现层次性结构和获得网络的低维嵌套。上述工作对专家分组的使用是将其从网络中排除,但有时,知道了节点的非拓扑属性可能会有助于社团结构的探测。基于这些已知属性,本文定义了类模块度目标函数,是经典的模块度与条件熵的线性组合。另外,本文还介绍了作者在读期间的两个其它方向的工作。一个是复杂网络中基于行为响应的疾病传播,建立了网络中具有行为响应的传播模型,在平均场近似下使用渝渗方法,计算出了传播阈值和传播范围,与模拟结果能吻合。另一个是城市交通模型中的动态交通灯策略,提出了两种动态交通灯策略,其中一种比经典模型中的交替策略要好。
[Abstract]:Around us, the complex system is widespread. In order to study complex systems, people made various efforts to establish a variety of theories, and the complex network is one attempt at the end of twentieth Century began to rise. Complex network is a complex system of an abstract, the abstract to seize the two points of complex systems: individual and interact with each other. There are three benefits to do so: the system can be simplified, reduce the complexity and dimension of the system; the system can be described by mathematical language of graph theory, provides an intuitive image; provides a unified framework for the study of different kinds of systems. The complex network is a simplified complex system, but still very complicated, this requires us to further reduce the dimension, to observe the network from different angles. From different angles to observe and describe the characteristics of complex networks, can find different aspects of the network For example, scale-free, small world characteristics. The research emphasis, the community structure is depicted from the large scale complex network structure perspective. The community structure is an important structure of complex network, this paper summarizes the importance of including: the community structure is helpful to our understanding of complex organization principle the network, the emergence of community structure in a real network, community structure is a bridge connecting the network structure and function, the community structure has a certain effect on the identification of network structure, the dynamic behaviors of community structure on the network to have a significant effect, provide a specific target observation network of the perspective of community structure for some, the community structure algorithm provides a validation platform. However, in many real networks, we often only know the topology, and community structure is unknown, which requires us to enter the community structure Line detection. For the detection of community structure, people have built a variety of methods, this paper mainly introduces the method of module and statistical inference method based on two. In order to compare the performance of these algorithms will need to be tested, is usually carried out in the artificial benchmark network has reference packet and real networks. In real network, reference the packet for experts in the field of additional information network are based on various detection algorithms and can be restored, this group is called expert group, often the default community structure represents the real network. The algorithm is required to be restored. Although the expert group is widely used in the detection of community detection algorithms, but there is little work focus on the assessment of the expert group itself. This paper proposes a new concept about the relationship between community structure and expert groups: completeness, known as division (either expert The packet is from the community detection algorithm) is a complete information network community structure. In order to study this problem, a new evaluation index of community structure definition: the exclusion of modularity, and based on the hole theory of statistical physics, a mathematic method principle. This paper found that in karate club network, expert group contains enough information network community structure. For the famous political blog network, beyond all expectations, the expression of expert group on community structure is not perfect, that there are hidden behind the unknown structure in the expert group, means that the relationship between community structure and expert groups need to re check. As a by-product, can this method is used for detecting the hidden community structure, hierarchical structure and found that access to the network of low dimensional embedded in the edge of the case does not delete the work on. The use of expert group is excluded, from the network but sometimes know detecting non topological properties of nodes may contribute to the community structure. These known properties based on the definitions of the class module of objective function is a linear combination of modularity and conditional entropy classic. In addition, this paper also introduces the authors work during the reading of two in the other direction. One is the spread of disease based on behavior in complex networks, with the behavioral response of the network propagation model is established in the mean field approximation using percolation method, calculate the propagation threshold value and the range, consistent with the results of another. Is a city traffic model in dynamic traffic light strategy, put forward two kinds of dynamic traffic light strategy, one of them is better than alternative strategies in the classical model.

【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】