复杂网络社团算法及其信息辨识应用研究

复杂网络具有三种特性，分别是小世界特性（Small World Theory）、无标度特性（Scale-free）和社区结构特性（Community Structure）。小世界特性即六度分离理论（Six Degrees of Separation），即图 1.1 所示（网络示例），其意思是社交网络中任何两个人所要取得联系的间隔人数不会超过六个，此特性与信息在网络中的传播具有着紧密的联系；无标度特性是指在一个网络图中，只有少数节点拥有大量的连接，而且图中大部分节点的连接数都很少，无标度特性与网络的鲁棒性分析有着密切的联系；社区结构特性指的是一个图中的节点具有集聚性，即可以对节点与节点之间相互连接的关系，进行社区分类划分，这是一种网络内聚的表现。在研究复杂网络的同时，各个领域诞生出了一些以复杂网络特性为基础的理论，比如：“二八法则”，经济学中认为 20%的人掌握着 80%的财富，并将其定义为“帕累托经济分配定律”；信息学中认为一个社区中的 10 个人，其中1 个人在创造信息，1 个人参与，其他的 8 个人只是旁观；“150 法则”，说的是一个人能够管理最多的好友数量也就 150 个。

............................

第二节   研究现状
学术界对于复杂网络的研究从未停止，复杂网络其中的奥妙也从未让学者们失望。现如今，复杂网络已经被运用到许多行业研究中。吴明功等人[1]将复杂网络理论运用到空中交通中，构建复杂网络模型，利用复杂网络特性对空中网络的复杂性进行了深度分析。王雪等人[2]基于复杂网络对中医中的俞穴配伍规律进行了分析和研究。祝鹏飞等人[3]基于复杂网络视角，运用复杂社会网络分析方法，

对外商直接投资和农村剩余劳动力之间的空间网络关联关系进行实证检验。能够看出，复杂网络理论在很多领域或是行业都具有研究价值，复杂网络视角下的研究，更是可以得到一些有意义的信息。复杂网络社团算法亦是如此。
利用复杂网络结构信息进行社团发现，能够更好地描述网络的拓扑结构，不仅可以发现复杂网络的独有特征，而且对于理解网络的动力学等方面有很大的帮助。在之前的几十年，社团结构分析在许多学科领域得到了众多学者和研究人员的关注和深入研究，不仅在社会学中，而且在生物学中均有实际的应用[4,5]。图分割算法是最早被提出用来解决社团发现问题的算法，但图分割算法需要在分割前指定分割的大小和个数，因此研究人员后来逐渐放弃了图分割法[6]。基于层次聚类的社团检测算法[7]是按照网络内节点之间的相似程度，根据相似程度的高低来完成社区检测任务。基于节点相似性[8]的社团检测算法是一种凝聚方法，其思想是通过在两个相似性大的节点之间增加边来发现网络中的社团结构。还有一种属于分裂方法的社团检测算法，这种社团检测算法基于节点相异性[9,10]，通过去除两个相异性大的节点之间的边来发现网络中的社团结构。任永功等人[11]在 2011年针对小型社区的发现，提出了一种利用社区局部信息进行社团划分的算法。2015 年，

Wang T.等人[12]提出了一种新的社团发现算法，该算法将节点间的余弦距离作为相似度量，通过设置余弦距离阈值和度阈值确定社区中的核心节点，改变余弦阈值和度阈值，利用模块化操作得到网络中最优的社团结构。2017 年，K. R. Zalik[13]在标签传播算法（Label Propagation Algorithm）的基础之上，提出了基于社团的定义和拓扑相似性的更新规则，该方法在划分社区质量上有所提高。

..........................

第二章  相关研究

第一节   复杂网络经典模型
本节将介绍几种经典的复杂网络模型，分别是规则网络、随机网络、小世界网络和无标度网络。

（1）规则网络
规则网络是最简单的一种复杂网络模型，它是指网络中的各个元素之间的关系结构都是规则的、有序的，也就是说网络中随机任取的两个节点之间的关系遵循已经存在的规则，一般情况下每个节点的近邻数目都相同。全局耦合网络（也称为完全图）、最近邻耦合网络和星型耦合网络是常见的三种具有规则拓扑结构的网络。

..............................

第二节   常用的社团算法
社团算法是社团发现算法的简称，是利用图拓扑结构中所蕴藏的信息从复杂网络中解析出其模块化的社团结构。学者们对社团算法的研究持续不断，从最初由 Michelle Girvan 和 Mark Newman 基于分类层次聚类思想并利用边介数提出的GN 算法，到 Raghavan 根据网络中存在的传播性将 LPA(Label  Propagation Algorithm) 算法引 入 社团算法，以 及 可以 运 用在重 叠 社区中的 CPM(Clique Percolation Method)算法，都见证了社团算法在不同方面的优良发展过程。但是社团类算法似乎并不存在一个最好的算法，真实数据中对于社团或者社区的定义千差万别，很难真正的对社团划分进行评判。社团算法发展至今，肯定存在被大众广泛应用的算法，接下来将介绍两种重要的社团算法。

（1）Louvain 算法
提到 Louvain 算法，首先要介绍一下模块度。最初研究社团算法之时，没有一个具体的评判社团算法结果优劣的方法。直到 2003 年，Newman[33]首次提出了模块度的概念，在不清楚划分社团结果的情况下，模块度能够作为一种标准，去衡量社团算法所得出的结果，从而能够评判社团算法的优劣程度。模块度作为一个数值，其取值在 0 到 1 之间，当社团划分的准确率越高，或者说社团算法划分效果越好的时候，那么模块度的值就越大。
............................

 

第三章  RICD 框架设计 ························ 24
第一节   问题定义 ····························· 24
一、问题描述 ·································· 24
二、框架描述 ························ 24
第四章  改进的谣言源检测算法设计 ································ 34
第一节   网络中源检测的因素 ··························· 34
一、网络结构 ····························· 34
二、谣言传播模型 ······························· 36 
第五章  总结与展望 ························· 46

第四章  改进的谣言源检测算法设计

第一节   网络中源检测的因素
信息源检测是指寻找某个人，或是某一地点，或是某一实体，如病毒性疾病、某一网络中的病毒或某一社交网络中的错误信息开始的地方。不同的领域内部的关系都可以用一个网络来表示，如计算机网络、社会网络、人们之间的关系网络等。网络中源检测的分类如下图所示，包括网络结构、常用的传播模型、中心度量和评价方法。

................................

第五章  总结与展望

复杂网络社团算法目前主要应用于社会网络分析中，它所挖掘出来的信息价值比较大。本文从文章开始介绍了复杂网络的研究背景，从而引入复杂网络社团算法，并由此引申社交网络上信息辨识方面的问题。接着分别对复杂网络社团算法、谣言检测算法以及谣言源的辨识进行了研究现状分析。
现如今大多数谣言检测方法都是基于机器学习算法，本文提出的 RICD 框架将复杂网络社团算法的作用发挥到谣言检测中去，框架中，在使用机器学习方法检测谣言后，对检测结果进行优化。此框架力图强调复杂网络社团算法对于谣言检测所发挥的积极作用，并在微博真实数据集上得到了相应的证实。对此，在谣言检测这一领域应该可以融入或者结合更多的方法或技术，使得更多的创新技术在学术上得以发展，使得学术上已经研究出来的方法模型，让更多的学术成果能够落地，尽早地运用到实际生活中去。
了解到社交网络上谣言不断，无法遏制谣言的传播，研究了复杂网络中谣言源检测的相关技术，介绍了复杂网络中影响谣言源检测的各种因素，对使用于谣言源检测的 MPA 算法进行了改进，提出的 IMPA 算法在现实社交网络数据集上得到了较好的应用，在准确率和执行效率方面都较 MPA 算法有一定的提升。
在研究本文中相关内容时遇到了许多的问题，至此提出对未来的展望：
（1）数据集的统一。想要分析真实的实时的微博数据或者 Twitter 数据，必须从微博官网或者 Twitter 官网上进行获取，但是想要从社交平台的 API 接口获取数据具有很多的限制和约束，不同时期、不同手段所抓取的数据会有所差异。而且在一些文献中，并未将其使用的数据集公开。即使有公开的数据集，格式大不相同，无法从根源相统一，不利于实验结果之间的相互比较，加上现在数据隐私的呼声越来越大，谣言检测的研究人员想得到大量且完整的数据集变得更加困难，这对于学术研究是一个不小的阻碍。
参考文献（略）