信息网络拓扑结构与内容相关性研究

论文摘要

互联网的普及大大推动了社会信息的网络化进程。包括Web、博客、即时通信、P2P资源共享等各种信息网络迅速发展。对大规模信息网络的规律性特征发现、信息网络的建模、信息网络社区发现以及信息网络应用研究,例如高效率信息搜索与信息定位、信息内容的深度挖掘以及信息动态传播机制和信息扩散行为的分析等是信息网络研究的现实需求,也是极具挑战性的研究问题。本文在详细观察了Web网络的拓扑结构特征以及拓扑结构与内容分布相互关系的基础上,以信息网络的物理连接拓扑结构与节点内容相关度分布之间的相互关系为主线,从网络特征、网络建模、社区分析及相关应用方面问题进行了深入细致地探讨:首先在验证了前人提出的Web网络拓扑结构特征基础上,进一步发现了信息网络所具有的一些新特征:1)网络微观颗粒度的拓扑结构聚团与内容聚团存在明显的映射关系,具体包括节点之间的物理连边概率与节点之间的内容相关度成指数比例关系、节点形成三角形拓扑结构的概率与节点内容相关紧密程度之间同样具有一种指数比例关系;2)网络节点连接度整体分布与节点内容相关度整体分布是线性无关的;3)网络微观拓扑结构中的存在很强的集聚性(平均聚团系数很高)。其次,针对当前的Web网络模型无法解释拓扑结构与内容分布之间的映射关系,提出了一种融合节点知名度和节点相关度的Web网络演化模型(PRCP Model)。从模型的理论推导、演化学习验证以及大规模实验验证表明,该模型既能解释网络节点连接度的幂律分布规律,又能产生与真实网络相类似的微观拓扑集聚现象;而更重要的是,PRCP模型能够很好地拟合真实网络中存在的网络微观粒度拓扑聚团与内容聚团之间的映射关系。由此,我们可以进一步推测出信息网络中“微观层次的结构与内容构造规则共同决定了网络整体的物理结构和内容分布”这一规律性的结论。最后针对信息网络社区发现和社区关系分析的实际需求,分析了当前基于物理连边密度这种单一尺度社区研究的不足,提出了一种多尺度、概率化的信息社区概念。新的社区概念考虑了物理连边密度和节点之间属性相关度等多种尺度,以连边和消息转移概率来综合定义信息网络中的社区,并在此基础上提出了相应的社区发现算法。从而可以发现更有实际价值的信息网络社区结构。

论文目录

• 摘要
• 第一章 引言
• 1.1 网络效应
• 1.2 复杂网络研究的基本问题
• 1.3 信息网络研究背景
• 1.4 本文主要贡献与组织
• 第二章复杂网络研究概述
• 2.1 基本概念与研究背景
• 2.1.1 基本概念
• 2.1.2 从规则网络、随机网络到复杂网络
• 2.1.3 复杂现实网络的分类
• 2.2 复杂网络的拓扑结构特征
• 2.2.1 连接度的分布与自由标度网络
• 2.2.2 最短路径与小世界效应（Small World Effect）
• 2.2.3 传递性与聚团系数
• 2.2.4 特征子图（motif，subgraph）
• 2.2.5 网络社区结构
• 2.2.6 介数（Betweenness）
• 2.2.7 网络的弹性（Network Resilience）
• 2.2.8 其他特征
• 2.3 复杂网络的建模
• 2.3.1 小世界网络模型
• 2.3.2 自由标度网络模型
• 2.3.3 几类有针对性的网络模型
• 2.3.4 产生高聚团系数的网络增长机制
• 2.4 与复杂信息网络相关的应用研究
• 2.4.1 网络传播机制研究
• 2.4.2 P2P网络中的资源共享与信息搜索
• 2.5 复杂网络研究的关键问题及研究趋势分析
• 2.6 本章总结
• 第三章Web网络的拓扑结构与内容相关性分析
• 3.1 Web网络的拓扑结构特征概述
• 3.1.1 基本概念
• 3.1.2 Web网络的拓扑结构特征
• 3.1.3 Web网络中内容分布特征
• 3.1.4 Web网骆拓扑结构分析总结
• 3.2 Web网络的拓扑结构与内容相关性分析
• 3.2.1 拓扑结构与内容相关性分布的度量概念
• 3.2.2 实验数据的准备
• 3.2.3 Web网络节点连边及节点内容相关性分析
• 3.2.4 Web网络传递性与内容相关性分析
• 3.2.5 拓扑结构与内容分布的关系分析总结
• 3.3 本章总结
• 第四章节点知名度与相关度融合的Web网络演化模型
• 4.1 基本问题概述
• 4.1.1 问题与背景
• 4.1.2 Web网络建模研究的回顾
• 4.2 PRCP模型
• 4.2.1 PRCP模型的基本思路
• 4.2.2 PRCP的连边倾向机制（PRC-PA）
• 4.2.3 节点与边的独立增长机制（Independent Growing，IG）
• 4.3 PRCP模型的理论分析
• 4.3.1 知名度与相关度融合的连边倾向机制（PRC-PA）分析
• 4.3.2 连边概率与成三角概率分析
• 4.3.3 PRCP网络的传递性分析
• 4.4 PRCP模型的学习验证
• 4.4.1 现有的网络模型发现模式分析
• 4.4.2 网络模型的学习与发现技术
• 4.4.3 针对PRCP模型的验证实验
• 4.4.4 实验结果与分析
• 4.5 PRCP模型的模拟实验与结果对比分析
• 4.5.1 实验说明
• 4.5.2 实验结果及相关模型对比分析
• 4.6 本章小结
• 第五章信息网络的社区发现研究
• 5.1 复杂网络社区研究的基本问题与研究背景
• 5.1.1 网络社区关系分析的研究背景
• 5.1.2 复杂网络中社区发现的基本问题
• 5.2 基于单一尺度（物理连边密度）划分的社区研究回顾
• 5.2.1 简单图社区定义及发现算法研究
• 5.2.2 基于Edge-Betweenness 或Modularity的社区发现算法
• 5.2.3 基于链接分析的WEB 社区发现算法
• 5.2.4 K完全子图（k-clique）连边密度社区
• 5.2.5 连边密度社区研究的特点总结
• 5.3 多尺度、概率化信息社区（δ-闭集，δ? Closure 社区）
• 5.3.1 从物理连边密度社区到多尺度的信息传播密集社区
• 5.3.2 δ-闭集与δ-闭集社区的定义
• 5.3.3 δ-闭集社区的特点分析
• 5.4 δ? Closure 社区的发现算法
• 5.4.1 δ? Closure 社区发现算法框架
• 5.4.2 单个节点的δ? Closure 求解的终止判定条件
• 5.4.3 δ? Closure 社区计算
• 5.4.4 算法复杂度分析
• 5.5 δ? Closure 计算方法与k-clique计算方法的实验对比分析
• 5.5.1 连边内敛度（ECR）
• 5.5.2 社区概率内敛度（DCR）
• 5.5.3 综合系数比较
• 5.5.4 实验结果分析
• 5.6 本章总结
• 第六章 总结与未来工作展望
• 6.1 本文的总结
• 6.2 进一步的工作
• 参考文献
• 作者简介
• 致谢