论文部分内容阅读
网络节点的亲密程度或近似特征使社交网络往往呈现出特定的社区结构,因此,社区划分是社交网络结构研究的重要手段之一,研究划分后的网络社区可以获得网络的内部结构、作用关系以及规律特性,从而更好地理解和应用网络。现有的多种社区划分算法主要利用节点间连接的密切程度进行社区划分。本文把网络理解为一个信息随机扩散的系统,即节点信息扩散到其他节点的分布情况反映了他们之间的密切程度,这与PageRank算法的排序原理相一致。在此基础上,提出基于PageRank算法和信息扩散原理的社区划分算法(PR-DCS)。PR-DCS算法依据信息扩散的随机游走性质,将PageRank中的排序向量扩展为信息扩散矩阵,利用该矩阵反应出的节点间密切程度,分析得到社区结构。通过将PR-DCS算法与其他代表性社区划分算法进行实验对比分析,确定了PR-DCS算法能够准确的提取网络的社区结构。结合PageRank算法中的威望概念和PR-DCS算法中的主观意愿概念,对PR-DCS算法做了进一步的优化。算法的核心思想是同一社区节点间的信息交流更通畅,他们之间的信息交流比不同社区内节点间的交流更快达到稳定值。算法通过计算节点每次信息扩散之后的信息变化量来确定信息量率先稳定的节点关系,社区的核心节点在信息扩散过程中会先达到稳态,将先达到稳态的关系中的节点划分在一起能够更准确地提取社区结构。实验证明了社区核心节点扩散值达到稳态的速度高于其他节点,在对同一社区的划分中,优化算法的模块度更高,其结果也能更好地解释真实的社区划分。在对算法的探索中,分析了信息扩散次数对于划分结果的影响,将“六度分割”作为约束信息扩散次数的理论依据,保证了信息扩散矩阵中元素含义的正确性:既可以防止因扩散次数的增多而导致元素值转化为节点的威望值,同时也可以保证节点的基础交流行为。实验证明,将信息扩散次数定义为6能够客观地约束节点交流程度,准确提取社区结构。