在线社会网络的结构化分析方法及应用研究

摘要

继科学计算和生命计算之后，面向网络化社会系统的社会计算已然成为学术界的研究热点和前沿课题。社会网络结构分析是社会计算的核心问题之一，深入理解社会网络的结构特性有助于提高社会生产效率、缓解社会矛盾、提高社会收益、解决社会问题，因此具有广阔的应用前景。现有的社会网络结构分析方法大多面向静态网络，无法满足在线社会网络的演变要求。此外，网络结构分析中固有存在的一些技术难点，如算法时间复杂度过高、需要先验知识、结构形态受限、数据维度过高等，同样限制了该领域的发展。针对传统社会网络结构分析方法中存在的不足，本着对现有方法进行改进、完善和发展，本文一方面研究如何设计在线式社会网络结构分析框架以满足在线网络的实时性要求，另一方面研究如何设计更具前瞻性的方法和理论以解决社会网络模体识别中存在的技术难点，最后，利用网络模体的结构特性，解决应用系统中存在的具体问题。归纳而言，本文的研究内容主要包括以下4个方面：
　　（1）多关系社会网络社区识别方法研究。相比于单质网络社区识别，多关系社会网络中的社区结构是隐含的、难以发现的。现有方法大多从结构表达能力上看待异构社区结构，进而多采用全局优化方法。这类方法在某些特定的网络类型求解中可能具有一定的优势，但缺乏普适性。例如当异构网络各层级内部的社交关系差别很大时，全局优化会使识别出的社区结果偏离真实社区，因此精度较低。此外这类方法忽略了各网络层级之间的关联性，因此社区内部节点间的交互程度可能很低，从而失去现实意义。本文将异构社区识别任务视为社交个体的局部选择过程，首先通过度量异构网络层间吸引力、同质网络节点游走可达概率，提出异构网络随机游走模型；然后对随机游走路径施以同社区互可达性约束，将各子网节点间的相似性度量，建模为随机游走的可达性度量；最后，将相似性函数推广到层次聚类，异构社区识别任务可以在较短的时间内迭代完成。
　　（2）在线社会网络社区识别方法研究。静态网络社区识别中普遍存在的社区重叠问题、参数依赖问题、社区形态约束问题在动态网络环境下的解决难度更大。一方面，已经被广泛认可的静态社区识别技术或理论大多无法适用于动态网络；另一方面，某些参量在网络演变时可能对社区结构造成不可预料的改变，这给动态社区识别中的实时性、精准性要求带来了严峻的考验。为解决这些问题，我们提出社区稳定性这一概念替代传统的基于结构的社区定义。社区稳定性基于节点间的同质性吸引，因此稳定状态的社区结构应满足社区内部节点具有较强的互吸引力，而分处于不同社区的节点尽可能不具有任何吸引力。该方法避免了传统社区识别中的结构约束，因此社区可以具有各种形状；进一步讲，社区稳定性的天然存在使得算法不必依赖于各种输入参数；由于社区边缘节点可能同时被不同的稳定核心吸引，因此所识别出的社区结构具有重叠性。在动态社区识别方面，我们将在线社区识别问题转化为社区稳定性的校准问题，进而动态社区结构可通过对历史社区校准而得。
　　（3）在线社会网络结构压缩方法研究。如果按数据存储规模进行划分，社会网络压缩研究可分为无损压缩和有损压缩两种。本文关注于网络结构的规模缩减，因此属于有损压缩的研究范畴。无损压缩方法虽然能够避免压缩损失，但存在压缩率极限，无法满足用户的实际需求。而在有损压缩中，时间开销过高、结构表达能力较弱、对动态网络匹配性较低是亟待解决的关键问题。本文提出一种基于结构相似性整合的两阶段动态网络压缩框架。在第一阶段，通过证明将压缩损失的差异性优化，转化为压缩过程中节点合并的局部选择优化，从而证明了静态网络压缩序列的线性时间复杂性；在第二阶段，以稳定压缩损失为前提，校准前一时刻的压缩表达以此避免算法的重复执行，在满足在线社会网络演变要求的同时提高了压缩效率。
　　（4）在线社会网络社区结构应用研究。在结构分析的应用层面，我们关注于移动互联网中的蠕虫遏制问题。现有的蠕虫遏制方案大多面向单质网络，无法遏制蠕虫的混合传播。此外，网络动态性带来的结构改变加大了蠕虫病毒的遏制难度。针对这些问题，我们提出一种基于社区的混合蠕虫双向反馈遏制系统。该系统借助了社区结构对蠕虫病毒的捕获能力。首先对社区边缘节点施以门禁免疫策略将蠕虫控制在社区内部；然后，提出分布式蠕虫标签转发策略，使未被蠕虫感染的节点快速达到免疫状态，从而降低了蠕虫在社区内部的传播速度；最后，提出一种节点信任性评估方法，通过收集节点的GPS信息、历史安全记录、交互频率，对可信性较低的节点限制通信，以此防止混合蠕虫的协同感染。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 主要研究内容

1.4 论文组织结构

第2章 多关系社会网络社区识别方法研究

2.1 引言

2.2 基本原理

2.3 基于随机游走的异构网络相似性度量方法

2.4 基于贪婪层次聚类的社区识别方案

2.5 实验结果与分析

2.6 本章小结

第3章 在线社会网络社区识别方法研究

3.1 引言

3.2 挖掘初始网络社区结构

3.3 在线社会网络社区识别

3.4 实验结果与分析

3.5 本章小结

第4章 在线社会网络结构压缩方法研究

4.1 引言

4.2 问题描述

4.3 压缩初始网络结构

4.4 在线式社会网络压缩

4.5 实验与结果分析

4.6 本章小节

第5章 在线社会网络社区结构应用研究

5.1 引言

5.2 相关工作介绍

5.3 蠕虫遏制系统及其工作原理

5.4 遏制系统组件设计

5.5 仿真实验

5.6 本章小结

结论

参考文献

攻读博士学位期间发表的论文和取得的科研成果

致谢