基于社区节点重要性社会网络压缩方法.ppt

基于社区节点重要性的社会网络 压缩方法 哈尔滨工程大学 计算机科学与技术学院 0 摘 要 针对目前图压缩方法中存在的时间复杂度较高、依赖先验知识设定参数、需要调节的参数过多、压缩有损、忽视网络社区结构等问题，提出基于社区节点重要性的社会网络压缩方法。该方法由基于贪婪策略的社区发现算法（GS）和社会网络压缩算法（SNC）两部分组成。GS算法采用拓扑势理论，不但可以实现社区发现而且可挖掘出社区中的重要节点。SNC算法以网络社区为压缩对象，在保持社区间的关联关系的前提下实现了无损压缩，并可在必要时保留社区中的重要节点或基本结构。方法的可行性和有效性通过实验进行了验证。 1 拓扑势理论简介（1） 拓扑势理论来源于核子物理学，可用于指导社会网络上的社区发现。在核子物理学中，核子间的非接触式相互作用通过核子场进行刻画。拓扑势理论借鉴了核子场理论，认为存在直接或间接关系的节点间存在相互的作用力。这种节点间的作用力，在拓扑势理论中被称为拓扑势，也象核子间的作用力一样会随着距离的增加而不断衰减，直至衰减为零。拓扑势理论中节点间的距离指的是节点间的拓扑距离，而非核子场理论中的欧氏距离。在拓扑势理论中规定一个节点的拓扑势即为其他节点对其作用力的加和。 1 拓扑势理论简介（2） 1 拓扑势理论简介（3） 1 拓扑势理论简介（4） 2 社区节点重要性分析（1） 从社区构成的层面来说，应用拓扑势方法发现的社区中的节点的重要性是存在差别的。此差别主要体现在以下的定理及推论中。 定理1 设节点 u、v 处于某社会网络中社区代表点 v* 的一条吸引链上，且 u 位于 v* 的第 a 跳，v 位于 v* 的第 a+1 跳，a = 0, 1, 2, …, h-1，则 u、v 对 v* 的拓扑势贡献量比值Ru←v(a,a+1) = 。 2 社区节点重要性分析（2） 推论1 设节点 u、v 处于某社会网络中社区代表点 v* 的一条吸引链上，且 u 位于 v* 的第 a 跳，v 位于 v* 的第 a+1 跳，a = 0, 1, 2, …, h-1，则 u、v 对 v* 的拓扑势贡献量比值Ru←v(a,a+1)1。 推论2 设节点 u、v、w 处于某社会网络中社区代表点 v* 的一条吸引链上，且 u 位于 v* 的第 a 跳，v 位于 v* 的第 a+1 跳，w 位于 v* 的第 a+2 跳，a = 0, 1, 2, …, h-2，则有Rv←w(a+1,a+2) Ru←v(a,a+1)。 2 社区节点重要性分析（3） 推论3 设节点 u、v、w 处于某社会网络中社区代表点 v* 的一条吸引链上，且 u 位于 v* 的第 a 跳，v 位于 v* 的第 a+1 跳，w 位于 v* 的第 a+2 跳，a = 0, 1, 2, …, h-1，则有Rv←w(a+1,a+2)= Ru←v(a,a+1)。 推论4 设节点 u、v、x、y 处于某社会网络中社区代表点 v* 的一条吸引链上，且 u 位于 v* 的第 a 跳，v 位于 v* 的第 a+1 跳，x 位于 v* 的第 b 跳，y 位于 v* 的第 b+1 跳，a, b = 0, 1, 2, …, h-1，且 ba，则有 Rx←y(b,b+1) = Ru←v(a,a+1) 。 2 社区节点重要性分析（4） 3 方法基本思想 从前面的分析可以知道，在拓扑势方法发现的社区中代表点的邻居节点的重要性是逐跳降低的。因此，本文压缩方法将首先基于拓扑势理论进行社区发现，然后再按层进行网络压缩。 图1即为在发现的社区上进行压缩的示意图。 4 实 验（1） 4 实 验（2） 实 验（3） 4 实 验（4） 5 实验分析 谢谢！ * * Books about US politics network Zachary空手道俱乐部网络 1.4571e+003 619.2763 1.0330e+003 154.8820 831.2309 4 3 181.8129 98.6741 142.2059 36.6679 121.7630 3 2 22.6869 15.7225 19.5772 8.6810 17.8365 2 1 Books about US politics (σopt=0.9803) Les miserables (σopt=1.0435) Word adjacencies (σop