复杂通信网络拓扑分析及社团抽取算法研究

摘要

手机作为现代社会交流通信的工具，能够很大程度上刻画出人与人之间的社会交往关系，因此通信网络的组成个体之间会依据社交关联形成复杂网络结构，这对社会网络的结构和人类行为动力学的分析有重大的应用价值。社团结构是复杂网络中最普遍的拓扑特征，社团间的连边稀疏，社团内部的连边紧密，而且社团还具有重叠性，即对于个人而言，可以同时属于多个社团。然而通信网络的规模极大，如何高效地分析网络的特征是急需解决的问题，而经典的社团发现算法需要分析网络全部拓扑，这使得其无法在超大规模网络上应用。另外，很多情况我们只关心网络的某个特定社团，而没必要用社团发现算法给出网络全部的社团结构。
　　针对以上问题，本文基于复杂网络相关理论，完成了以下两方面的工作。
　　第一，提出多重时变通信网络模型，此模型通过多重连边动态实时的记录用户之间的多次通话，边上权值代表通话的时间属性，经通话数据预处理后，便可以通过网络读出用户完整的通信行为。然后对网络的整体和个体方面，分别对度之和、平均度等演化过程进行分析，同时对通话时长、通话时间间隔等的分布情况进行探究，得出人类行为的普遍规律，为社团抽取提供现实依据。
　　第二，对于一个人，可以与家人、朋友具有紧密联系，形成明显社团;同事和工作上的业务伙伴也会形成社团。本文的目的就是将在超大规模的通信网络上，对某特定个体的不同社团进行抽取。因此提出社团抽取算法，本算法无需事先获取网络的全部拓扑结构，采用社团搜索和社团判定相结合的思路，可有效的抽取结构未知的通信网络上的某个特定社团，从而使分析超大规模网络社团结构成为可能。本文首先在具有先验知识的网络对此算法的有效性和可行性做初步判断，然后在大规模仿真网络上进行实验，实验结果表明此算法的准确性和高效性。接着对影响算法准确度的初始节点的选取方面做进一步的探究，发现初始节点所处位置对算法结果影响很大。最后针对多重时变通信网络，对此算法进行改进，通过时序的边上权值的关系划分出不同的时间社团，进而抽取某个体的不同社团，分析抽取结果，得出相应结论。

目录

声明

摘要

第1章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．2．1 复杂网络理论与社团结构研究现状

1．2．2 时变通信网络研究现状

1．3 主要研究内容

1．4 论文的组织结构

第2章 相关技术

2．1 复杂网络

2．1．1 复杂网络简介

2．1．2 复杂网络的基本拓扑特征

2．1．3 模型网络

2．2 复杂网络社团研究的一些基本概念

2．2．1 社团的定义

2．2．2 模块度指标

2．2．3 层次性

2．2．4 重叠性

2．3 具有代表性的复杂网络社团发现算法

2．4 本章小结

第3章 个人通信网络构建及其拓扑分析

3．1 多重时变通信网络

3．1．1 多重时变通信网络的定义

3．1．2 多重时变通信网络的构建

3．2 通信数据集

3．2．1 通信数据集的基本概况

3．2．2 数据预处理方法

3．3 多重时变通信网络的拓扑分析

3．3．1 整体网络拓扑分析

3．3．2 个体网络拓扑分析

3．4 本章小结

第4章 基于时变通信网络的社团抽取算法

4．1 问题描述

4．2 CEA算法

4．2．1 算法思路

4．2．2 算法定义及描述

4．2．3 算法实验结果及分析

4．2．4 初始节点集选取探究

4．3 ECEA算法

4．3．1 问题描述及相关定义

4．3．2 算法描述

4．3．3 实验结果展示与分析

4．4 本章小结

第5章 总结与展望

5．1 工作总结

5．2 进一步研究工作

参考文献

致谢

攻读硕士期间参加的科研项目