基于社区节点重要性的社会网络 压缩方法 哈尔滨工程大学 计算机科学与技术学院

0 摘 要 针对目前图压缩方法中存在的时间复杂度较高、依赖先验知识设定参数、需要调节的参数过多、压缩有损、忽视网络社区结构等问题，提出基于社区节点重要性的社会网络压缩方法。该方法由基于贪婪策略的社区发现算法（GS）和社会网络压缩算法（SNC）两部分组成。GS算法采用拓扑势理论，不但可以实现社区发现而且可挖掘出社区中的重要节点。SNC算法以网络社区为压缩对象，在保持社区间的关联关系的前提下实现了无损压缩，并可在必要时保留社区中的重要节点或基本结构。方法的可行性和有效性通过实验进行了验证。

1 拓扑势理论简介（1） 拓扑势理论来源于核子物理学，可用于指导社会网络上的社区发现。在核子物理学中，核子间的非接触式相互作用通过核子场进行刻画。拓扑势理论借鉴了核子场理论，认为存在直接或间接关系的节点间存在相互的作用力。这种节点间的作用力，在拓扑势理论中被称为拓扑势，也象核子间的作用力一样会随着距离的增加而不断衰减，直至衰减为零。拓扑势理论中节点间的距离指的是节点间的拓扑距离，而非核子场理论中的欧氏距离。在拓扑势理论中规定一个节点的拓扑势即为其他节点对其作用力的加和。

1 拓扑势理论简介（2）

1 拓扑势理论简介（3） Books about US politics network

1 拓扑势理论简介（4） Zachary空手道俱乐部网络

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，且 b>a，则有 Rx←y(b,b+1) = Ru←v(a,a+1) 。

2 社区节点重要性分析（4） 前述差别具体体现在表1中。 表1 若干网络的Ru←v(a,a+1) 节点u 开代表 点v*的 跳数a 节点v 2 社区节点重要性分析（4） 前述差别具体体现在表1中。 表1 若干网络的Ru←v(a,a+1) 节点u 开代表 点v*的 跳数a 节点v 离开代 表点v*的 跳数a+1 Karate Club (σopt= 1.0204) Dolphin Society (σopt=1.1782) Word adjacencies (σopt=1.0043) Les miserables (σopt=1.0435) Books about US politics (σopt=0.9803) 1 2 17.8365 8.6810 19.5772 15.7225 22.6869 3 121.7630 36.6679 142.2059 98.6741 181.8129 4 831.2309 154.8820 1.0330e+003 619.2763 1.4571e+003

3 方法基本思想 从前面的分析可以知道，在拓扑势方法发现的社区中代表点的邻居节点的重要性是逐跳降低的。因此，本文压缩方法将首先基于拓扑势理论进行社区发现，然后再按层进行网络压缩。 图1即为在发现的社区上进行压缩的示意图。 图1 社区压缩示意图

4 实 验（1） 空手道俱乐部网络上的2跳压缩

4 实 验（2） 空手道俱乐部网络上的1跳压缩 空手道俱乐部网络上的0跳压缩

实 验（3） 海豚社会网络上的2跳压缩

4 实 验（4） 海豚社会网络上的0跳压缩 海豚社会网络上的1跳压缩

5 实验分析 表2 社区压缩率数据表 网络名称 社区名称 社区节点 数目 压缩所至跳数 2 1 空手道俱 乐部网络 C1 24 0.2917 5 实验分析 表2 社区压缩率数据表 网络名称 社区名称 社区节点 数目 压缩所至跳数 2 1 空手道俱 乐部网络 C1 24 0.2917 0.9583 C34 27 0.2222 0.3333 0.9630 海豚社会 网络 C14 51 0.4314 0.7451 0.9811 C17 23 0.1304 0.5652 0.9565 C20 40 0.3750 0.7500 0.9750

谢谢！