Measuring Node Contribution to Community Structure With Modularity Vitality

用模块性生命力度量节点对社区结构的贡献

摘要

社区感知中心性是网络科学中一个新兴的研究领域，关注节点在社区结构中的重要性。先前的方法扩展了经典的中心性度量来解释社区结构，而与社区检测理论几乎没有联系。本文提出集群质量活力度量，即模块度活力，一种基于中心性和社区检测理论的社区感知度量。模块度活力量化了节点对社区结构的积极或消极贡献，表明节点作为社区桥梁或枢纽的作用。推导了一种高效算法，时间复杂度O(M+NC)。通过移除中心节点来系统地分割网络，并发现模块度活力始终优于现有的社区感知中心性度量。在一个百万节点的基础设施网络上，基于社区理论的有效性要高出8倍以上。没能推广到社交媒体通信网络，因为社交媒体对所有社区感知的中心性攻击都表现出极大的鲁棒性，表明基于用户的干预措施来减少错误信息的传播是无效的。最后，证明模块度活力为社区欺骗提供了一种新的方法。

1.介绍

传统上，中心性度量被定义为图不变量，但社区在网络中可以有多种不同且有意义的定义。

问题：给定一些社区的定义，网络中的每个节点有多重要？当考虑社区结构时，节点的相对重要性可能会发生变化。

本文将考虑社区结构的中心性度量称为“社区感知中心性度量”，此类问题结合中心性和社区结构概念，应用范围广，本文展示应用有：传染病免疫策略、大型基础设施网络的稳健性测试、基于隐私的数据过滤策略。

以往方法的不足：大多数现有的社区感知中心性指标通过分别考虑社区内部和社区之间的联系来扩展经典的中心性，然后应用加权和来获得单个分数。这种方法最终没有深入了解节点所扮演的角色，枢纽节点和桥接节点取值相近，无法区分。加权方案是人工主观制定，不是从社区理论中推导出来的。

灵感：考虑纽曼提出的“社区中心性”，度量了节点对社区结构的“潜在”贡献，一种经典的中心性度量，独立于任何社区划分定义。本文提出测量在特定的社区划分中节点对社区结构的实际贡献。得到了基于社区发现理论的社区感知中心性，不受人工制定加权方案的约束。

vitalities 以前只应用于经典的中心性度量，因此，被定义为只将图作为自变量的函数。本文将生命力/活力定义为一个以图及其社区划分为自变量的函数。消极影响意味着节点连接各个社区，桥接作用；积极影响代表社区枢纽作用。

重点：将活力度与模块度相结合，满足度量集群质量和节点中心性，对原始模块度函数的改进，提出计算模块度活力，时间复杂度O(M+NC)。

测试：宾夕法尼亚公路网、2019年加拿大大选讨论中收集的大型推特网络。

最后本文证明模块度活力可以用来执行贪婪攻击以降低模块度，为社区欺骗提出新的方法——改变网络连接。在实验中以2%的节点和45%的边为代价，降低了41%的模块度。已知通过删除节点来降低模块度的方法的效果随着节点删除越多而递减，表明社区欺骗的可拓展策略是删除边，不同于典型策略——重连边。

2.相关工作

A.预备知识

定义2.1 图（略）

定义2.2 图分割：

\[\xi = \left \{ \gamma_{1}, \gamma_{2}, \dots, \gamma_{C} \right \}, \gamma_{i} 为社区 i 的节点集 \\ \gamma_{i} \cap \gamma_{j} = \emptyset, i \ne j,\forall i,j \in \left \{1, \dots, C \right \} \\ \gamma_{1} \cup \gamma_{2} \cup \dots \cup \gamma_{C} = V,C=\left | \xi \right | \]

定义社区向量

\[c = \left [ c_{1}, c_{2}, \dots, c_{N} \right ],\\ c_{i}表示节点i的社区 \]

定义2.3 节点的总度和节点的社区度

\[k_{i} = \sum_{j} A_{ij} \]

\[k_{i}^{c} = \sum_{j=1}^{N} A_{i,j} \delta (c_{j},c) \]

\[\delta (a,b) = \left \{ \begin{array}{rcl} 1 & & a=b\\ 0 & & otherwise \end{array} \right. \]

定义2.4 内部度和外部度

\[k_{i}^{internal}=k_{i}^{c_{i}} \]

\[k_{i}^{external}=\sum_{j=1}^{N} A_{i,j}(1-\delta (c_{i},c_{j}))=k_{i}-k_{i}^{internal} \]

图G的内部连接数量：

\[M^{internal}=\frac{1}{2} \sum\nolimits_{i,j} A_{i,j} \delta (c_{i},c_{j}) \]

定义2.5 组分数

\[\mu_c=\sum_{v_{i} \in \gamma_{c}} \frac{k_{i}^{internal}}{k_{i}}=\sum_{v_{i} \in \gamma_{c}} \frac{k_{i}^{c}}{k_{i}} \]

B.模块度与分组

定义2.6 模块度

\[Q(G,\xi)=\frac{1}{2M} \sum_{i,j} \left ( A_{i,j} - \frac{k_{i}k_{j}}{2M} \right ) \delta (c_{i},c_{j}) \]

Louvain算法有缺陷，故本文采用Leiden算法，比Louvain快，弥补了Louvain的缺陷。

C.网络中心性度量

Newman，定义社区中心性，基于模块度矩阵的特征向量，没有度量节点的实际贡献而是对模块度的潜在影响。缺点：1、潜在影响和实际贡献不同。2、只使用图结构的方法无法适应不同的图划分。3、模块度矩阵内存效率低。

Masuda，采用特征值的方法，基于Restreop提出的动态重要性，邻接矩阵的最大特征值与在该图上扩散的容易程度有关。基于这一事实，根据从节点移除时最大特征值的变化来对节点进行动态重要性排序。“mod-strategy”，应用于群体网络，计算效率高。

节点基于以下方程排序：

\[M_{as_{i}}=(2 \tilde{u}_{c_{i}}-x) \sum_{c \ne c_{i}}\tilde{u}_{c}k_{i}^{c} \]

\[x=\frac{1}{\tilde{\lambda}}\sum_{c\ne c_{i}}\tilde{u}_{c}k_{i}^{c} \]

\[\tilde{\lambda}群网络最大特征值，\tilde{u}相对应的特征向量 \]

Gupta，社区中心性“commn-centrality——CC”

\[CC_{i}=\left ( 1-\frac{\mu_{c_{i}}}{\left | \gamma_{c_{i}} \right |} \right ) \frac{k_{i}^{internal}}{max_{v_{j} \in \gamma_{c_{i}}}k_{j}^{internal}}\times R_{c_{i}}\\ +\left ( 1+\frac{\mu_{c_{i}}}{\left | \gamma_{c_{i}} \right |} \right ) \left ( \frac{k_{i}^{external}}{max_{v_{j} \in \gamma_{c_{i}}}k_{j}^{external}} \times R_{c_{i}} \right )^{2} \]

\[R_{c_{i}}由用户定义，但通常选择R_{c_{i}}=max_{v_{j} \in \gamma_{c_{i}}}k_{j}^{internal} \]

（有缺陷，外部度在稳健性测试时容易为0，不考虑）

Ghalmane，邻近社区的数量中心性（the number of neighboring communities centrality）：计算节点直接邻域中的社区数量，定义为bi

社区枢纽桥梁中心性（CHB）：

\[CHB_{i}=\left | \gamma_{c_{i}} \right | k_{i}^{internal} + b_{i}k_{i}^{external} \]

内部中心性：

\[\Gamma^{internal}(G)=\Gamma(G^{internal}) \]

加权模块度中心性（WMC）：

\[WMC_{i}=\mu_{c_{i}}\Gamma_{i}^{internal}+(1-\mu_{c_{i}})\Gamma_{i}^{external} \]

本文，模块度中心性调整版本（AMC）：

\[AMC_{i}=(1-\mu_{c_{i}})\Gamma_{i}^{internal}+\mu_{c_{i}}\Gamma_{i}^{external} \]

优先对桥梁加权，曾被定义为加权社区枢纽桥中心性。

Masuda以外的都依赖内部外部中心性加权方案，权重是主观观察的。Masuda的是从理论推导出来的，但基于网络连通性。

定义 2.7 网络活力：

\[V_{f}(G,i)=f(G)-f(G-{i}) \]

定义 2.8 社区感知活力：

\[V_{f}(G,\xi,i)=f(G,\xi)-f(G-\{i\},\xi-\{i\}) \]

f可选，选择f为模块度函数，时间复杂度O(M+N)，与其他度量不同，模块化活力既显示了节点的中心性，也显示了节点以何种方式为中心。

D.评价指标：SIR模型和网络稳健性

SIR模型：一种基本流行病模型。节点状态：1、易感染；2、被感染；3、康复。感染概率p，康复概率r，被感染节点数量表示流行榜规模。

网络稳健性（Network Robustness）：反应网络对攻击的应对能力，了解网络在缺失节点或边的情况下如何反应。

网络碎片化（Network Fragmentation）：评估攻击有效性，片段化σ可以定义为剩余最大组件Nρ的尺寸与图的初始尺寸N之间的比例，其中ρ是移除节点的分数。

\[\sigma(\rho)=\frac{N_{\rho}}{N} \]

基于模块的攻击（Module-Based-Attack——MBA）：节点只有在最大组件中以及连接组时才会受到攻击。

Holme，两种攻击风格，initial和recomputed

E.社区欺骗

保护易于识别的敏感数据，应该模糊社区结构。因此，目标是编辑网络以防止特定社区被检测到。

基于模块度的欺骗：重新连接边使社区的模块度最小。

Chen Q-Attack：编辑网络以最大限度地减少整个网络分区的模块性，而不仅仅是单个社区。（无可拓展性）

本文展示模块度活力可以用于整个网络执行社区欺骗，通过移除所有连接到具有最高模块度活力的节点的边。有利于保持现有连接的准确，仅改变度分布。在社交媒体设置中，这相当于隐藏用户关注的流行帐户，而不是重新连接个人关注关系。

3.模块度活力的计算

模块度活力：

\[V_{Q}(G,\xi,i)=Q(G,\xi)-Q(G-\{i\},\xi-\{i\}) \]

单纯计算模块度O(M)，则计算模块度活力O(MN)。

高效更新模块度的方法：

\[Q(G-\{i\},\xi-\{i\})=\frac{M^{internal}-k_{i}^{internal}}{M-k_{i}}\\-\frac{1}{4(M-k_{i})^{2}}\sum_{\gamma_c \in \xi}(d_{c}-h_{i,c})^{2} \]

\[h_{i,c}=k_{i}^{c}+k_{i}\delta(c,c_{i}) \]

单个节点O(M+C)，所有节点O(M+NC)

4.方法

A.基于碎片化的评价

网络碎片化更易计算和解释，测试了MBA有效分割网络。

免疫或碎片化策略有效性取决于删除多少节点，为衡量整体有效性，对碎片化函数求积分。积分值越低，策略越有效。求最小化的成本函数：

\[C_{\rho}=\int_{\rho}\sigma(\rho)d\rho \]

B.攻击策略

Holme两种攻击策略：

1、初始化。所有节点计算一次中心性度量，选择前k个被攻击。如算法1所示。问题：删除一个节点后剩余节点的中心性改变，该策略无法检测到，选择的节点不再位于中心位置。

2、重新计算。节点移除后重新计算度。算法2所示。问题：计算开支高昂。

Cuhna提出更复杂策略（MBA）：仅通过攻击连接社区的节点来引入基于群体的结构。此外，仅攻击当前最大组件中的节点。在重新计算最大组件时，不重新计算中心性度量。算法3所示。

本文对小型生成网络采用I，R，MBA攻击策略；对PA-Road和Twitter采用”I”策略。结合度和局部社区感知中心性度量：Masuda(Mas)，CHB，WMC-D，AMC-D，Degree。以两种形式进行比较，1、原始模块度活力，从负到正攻击，以便针对社区桥梁。2、考虑模块度活力绝对值（AMV），根据节点对群体结构的整体贡献来定位节点。

第三种形式，从正到负攻击，因执行得很差被省略。

5.网络碎片化

A.生成网络

高密度ER网络模拟集群，随机大小的”cells”，”cells”之间通过随机节点相连，生成组到组的蜂窝网络，参数：

生成100个网络，每个网络八种社区感知中心性度量和三种攻击方案共24次攻击，记录Cρ和Cη，计算平均成本由下表所示。Leiden算法得平均模块度为0.91。

模块度活力最优，即最佳社区感知中心性度量。表明蜂窝网络中社区桥节点比枢纽节点更重要。

B.PA公路网

大型基础设施网络的特性：高模块度，低最大度。有利于基于组的方法，不利于基于度的攻击，像MBA这种有效方法需要更大的计算代价。

1088092个节点，15418988个边。莱顿法得到499个社区，模块度0.990，最大度为18。

移除1.6%的最大模块度活力的节点可以有效地使最大组件归零。移除正值和绝对值结果相近。

之前基于度的攻击表示PA似乎是稳健的，但其实社区中心性方法证明它很脆弱。

C.加拿大大选推特网

继续使用网络碎片化，因为与扩散有关。被移除的能分割网络的用户正是能够有力传播信息的用户。

7523125节点，130086491边。莱顿法得到557个社区，模块度0.691。

mv在点移除上表现极差，但在边移除上比其他方法好。其他方法移除10%-30%节点其实移除了95%的边。以上表明具有较高度的网络需要集成方法或者枢纽优先的方法来有效分割网络。又表明这类网络具有极高的鲁棒性。

D.讨论

在三个实验中，基于模块度的方法是有效的。PA中，模块度活力是度、WMC、CHB的8.5倍，与Mas和AMC类似，在Twitter中无效。但AMV可以解决，以为着攻击社区桥梁是不够的。

肯德尔秩相关系数（Kendall-Tau）：了解中心性排序的相似性。取值(-1,1)，1表示两个排列完全一致，-1表示完全相反，0表示没有明显相关性。

Deg具有高相关性；-0.94表明PA网中大多数节点是社区枢纽，选举网类似，相对较小。这结果与PA的高模块度性质一致，且模块度远高于选举网。

总的来说，优先攻击桥梁节点效果好；在社交网路中仅攻击桥梁还不够，需要同时攻击中心，但网络仍具有很强的鲁棒性。

社交网络中两种角色都是关键，鲁棒性既是优点又是缺点，既意味着许多用户拥有传播信息的能力，又意味着以用户为基础的干预措施无效。

6.社区欺骗

各种攻击都在增强模块度，模块度活力是最有效的，因此对于社区欺骗，需要攻击社区枢纽来最小化模块度，故最有效方案是，基于重新计算、反向的模块度活力攻击。更快的近似方法是初始、方向的模块度活力攻击。

实验（快速近似策略）：

删除社区中的流行账户以保护用户不被发现所处的真正社区。

问题：什么情况下删除网络数据的成本大于减小模块度带来的好处？

如果只是关心节点，代价很小；如果边很重要，代价就很大。

小型网络和非贪婪法的替代方案留待以后研究。

该攻击可以和之前研究的边重连攻击相结合。

其他应用：通过节点过滤以获得更多可解释的组。

7.总结

社区感知的中心性度量尝试量化在网络分割后，中心节点的重要性如何。当前社区感知中心性理论与社区理论联系不够紧密。本文提出的方法由模块度方程推导而来，与社区理论联系紧密。

本文提出一种可扩展的模块度活力方法，比一般朴素方法计算快一个引子N，可用于大规模网络分析。

与其他方法不同，模块度活力既量化了节点的重要性，还解释了节点所代表的角色。

高模块度网络中社区桥的节点更重要；社交网络中两个角色都重要，且社交网路稳健性高。

社交网络鲁棒性来源未知，可能与较多的社区桥节点有关。相反，高模块度网络社区桥节点很少。

基于用户的干预不是打击错误信息传播的有效策略。

社区欺骗方面，以前的遗传方法不能应用于大规模网络。

社区欺骗是一种组合优化问题，肯定有更好的解决方法，模块度活力贪婪法可以作为基线。

模块度是集群度量方法之一，可以考虑将活力应用于其他方法可以得到不同的观点。

附录：名词解释

“graph invariant”——*** 图不变量***：对于图上的一个映射，如果对每个同构图它均取相同的值，则这样的一个映射称为一个图不变量，一个图的顶点数和边数就是两个简单的图不变量，图中两两相邻的最大顶点数也是图不变量

同构图：假设G=(V,E)和G1=(V1，E1)是两个图，如果存在一个双射m：V→V1，使得对所有的x,y∈V均有xy∈E等价于m(x)m(y)∈E1，则称G和G1是同构的，如图。

<img alt="" data-attachment-key="I28TSB3I" width="1261" height="718" src="attachments/I28TSB3I.png" ztype="zimage"> 这样的一个映射m称之为一个同构，如果G=G1，则称其为一个自同构(automorphism)。用符号? ≅ ?′表示，直观理解为，可以通过将图G的顶点重新标号，使之与图G'完全相同，则G与H同构。