基于复杂网络的社区检测算法研究与实现

发布时间：2020-05-03 17:10

【摘要】：复杂网络的研究是近年来的一个热点。在现实生活中,生物基因网、物联网、人际关系网、互联网等等形成了各种各样的复杂网络结构。社区检测的出现就是为了观察复杂网络的结构,研究复杂网络结构的特性。社区检测是一个将杂乱无序的网络结构转变成合理有效的网络结构的过程方式,其处理对象是网络中的联系、拓扑结构、个体等(抽象为网络图中的边、节点等),并具有其各自的属性(例如边的权重、方向,节点重叠度等),社区检测利用特定算法以及网络本身的特性处理社区划分过程。社区检测能够将复杂网络结构化,进而帮助人们发现社区的内在属性,改进社区的交互形式。复杂网络的社区结构和网络的功能有着紧密的关系(如鲁棒性、传递性等),因此找出网络的正确社区结构并分析相关性质具有重要意义,基于点边比率的模块度社区划分标准是目前最常用的衡量网络社区结构划分好坏的度量,但存在一些无法克服的问题,也存在resolution limited问题,这就需要改进方法来提高社区划分的准确度。本论文提出了一种新的基于互信息与信息熵联合评判的的社区检测质量评价方法,该方法很好地避免了resolution limited问题,将信息传递的有损拓扑压缩过程映射到社区划分过程,利用信息量计算方法替换模块度计算方法,大大提高了算法划分结果的准确度。并在此基础上将非重叠网络社区划分方法进一步优化,加入重叠节点判断机制,使其能针对重叠网络结构进行社区划分,得到准确度较高的划分结果。本文的研究从互信息结合信息熵的双重角度揭示社区划分中更深层次的本质特征,加以建模实现,发现和揭示其中的规律,并给出与其他经典算法(例如GN算法、FastGN算法、LFM算法和CPM算法等)的实验结果的比较和分析。
【图文】：

结构图,复杂网络,结构图

计算机互联网技术的发展十分迅速[1]，，带动人类社会迈入们生活在各式各样的复杂网络当中。复杂网络[2]是具有一中个体之间相互联系、相互作用，丰富的信息蕴含在整样。各个领域的研究中都蕴含着复杂网络，研究复杂网络的有效信息，帮助分析网络特性，促进复杂网络的发展。分析已经成为我们共同的极具挑战性的研究课题。层面上来说，网络是可以用图像来表示。网络图基本上都边和权重。每一个节点表示关系中的实体，代表了一个城至一个人等等。每一条边表示实体间的联系，它可以代表中的一条光纤、社会关系网中的一种联系或者财富网络中值表示网络中的占比，代表实际网络中节点之间的关系的中的重要程度等。下图 1-1 就是一个复杂网络结构图。

示意图,社区,社区结构,情况

华南理工大学硕士学位论文社区结构 X 和划分后社区结构 Y 之间，Y 包含 X 的互信息评判标准表达式如下(;)(;)(,)(;)jijNiMjEiI XY IXY PXYIXY（其中，P(Xi,Yj)表示每一次社区划分中，任一节点由社区 Xi划分到社区 Yj中的式定义为：(,)(|)()ijjiiP XY PYX PX（其中，P(Yj| Xi)表示划分前在社区 Xi的节点在划分后被划分到社区 Yj的概率，划分前网络中的节点属于社区 Xi的概率。每次社区划分时，只需要考虑两种划分情况，如图 3-1：
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;TP301.6

【参考文献】