先有领袖后有边，
边边相顾成社团，
社团不知身是点，
点聚缘尽在无边。
社会网络分析是一门涉及信息学、数学、社会学、管理学、心理学等多学科的研究。在过去的十年间，在线社交媒体的发展为人们提供了一个独具魅力的知识、兴趣分享平台。社交网络的繁荣极大地丰富了我们的日常生活，同时也给传统社会网络分析带来了挑战。以节点影响力及其最大化研究为例，个体之间的各种交互行为和庞大的数据规模令很多研究者望而却步。为了解决复杂社会网络中节点影响力分析问题，本文主要介绍节点影响力评价及其选取策略，挖掘网络中的重要节点并分析影响力最大化问题，而本文的主要思想用上面的几句打油诗来概括。
节点影响力相关研究有几个相似的话题，如节点排序（Node ranking）、节点中心性（Node centrality）、关键节点挖掘（Key nodes identification）、影响力最大化（Influence maximization）等。本质上讲可分为两步：节点排序和节点选择。单纯地对网络中的节点进行排序，的确可以找出最重要（或最关键、最有影响力）的节点，传统指标度、介数、接近度中心性都已经非常完善了，但也存在这样或那样的问题（如选择性忽略、计算复杂度高等）。因此，本研究首先提出了一种简单高效的节点影响力度量方法（INF）[1]，然后设计了一种基于最优影响力的邻居扩展策略的层次挖掘方法（MINE）[2]，能够从这两个角度对网络中的重要节点进行挖掘，且通过MINE的组合策略，能够使影响力最大化。
首先，节点的影响力指标 考虑目标节点的邻居的度的倒数（\(I N F(i)=\sum_{j \in \Gamma(i)} \frac{w_{i j}}{k_{j}}\)，可以理解为目标节点的邻居对目标节点的关注程度，在无权网络中 \(w_{ij} = 1\), \(j\) 是 \(i\) 的一个邻居），也就是邻居节点的度越小，能够给目标带来的关注就越大，因此INF指标对能够吸纳孤立节点的目标节点比较友好，而这种友好导致的效果就是增强网络连通性的重要手段——因为能够将非连通部分连通起来，从某种程度上发挥了“桥梁”的作用（参考了介数中心性的指导思想嘛
），同时，对于邻居数较多的目标节点也非常友好，因为每多一个粉丝，都能为目标节点增加一点知名度，哪怕是非常小的一点关注（度中心性的思路
），作为一款同时结合了度和介数想法的指标，在识别具有影响力的节点方面，自然不会太逊色（事实也确实证明，在SIR实验及删除节点测算网络连通性的比较中发挥出色）。仅仅有了基础的节点排序方法，对于促使网络节点影响力最大化还远远不够。因此，本文进一步设计了重要节点的选取策略——基于最有影响力的邻居扩展（MINE）。从笨理儿上想，如果完全按照某个指标从大到小选取，很可能存在高度重叠情况（无标度特性导致了非均匀分布）。因此，重要节点的选取应尽可能分散，形成骨干网络。那么问题来了：如何分散呢？节点着色问题提供了一个很好的思想——拒绝邻居[3]，私以为确有其理，但还不够。现在跳出来，从社会网络的形成过程入手，社交网络的形成本身就是由于人的参与构成了一个个小圈子（或者自我中心网络，ego-network），这些小圈子的差异化和重叠性构成了复杂的社会网络。《论语》里说：“三人行，必有我师焉。择其善者而从之，其不善者而改之。”，所以每个小圈子必然有个领袖人物的存在，而其他大部分人对领袖人物持续关注且彼此间师出同门必然少不了联系，久而久之，也就形成了社团（community）。这也就解释了开篇的那一句：先有领袖后有边，边边相护成社团。
问题似乎越发明朗了，是不是找出各个社团中的领袖，影响力最大化问题就迎刃而解了呢？私以为还不足矣。如果我们上升一个高度看，那么就会发现这样找出来的领袖可能遍地都是，如有限定的领袖个数很少，又该如何选取呢？考虑层次聚类的思想，也就是说小社团之间的组合，其实是一个更高级别的社团，而之前的社团仅仅被抽象为一个个相对分散的超级节点（super-node）。举个例子，一个研究团队必有学术带头人，若干个相近的研究团队形成了院系，而相近的院系组成了一个科研单位，若干个科研单位的组合体现了国家或民族的科研水平，而众多国家级团队的研究水平决定了地球村的技能树……所以，这种层级关系必然是一种迭代过程，终归于一点，即彼此不再区分你我，没有边的存在——社团不知身是点，点聚缘尽在无边。
参考资料：
- Huang, X.; Chen, D.; Wang, D.; Ren, T. Identifying Influencers in Social Networks. Entropy 2020, 22, 450. https://doi.org/10.3390/e22040450
- Huang, X.; Chen, D.; Wang, D.; Ren, T. MINE: Identifying Top-k Vital Nodes in Complex Networks via Maximum Influential Neighbors Expansion. Mathematics 2020, 8, 1449. https://doi.org/10.3390/math8091449
- Wang, D.; Yan, J.; Chen, D.; Fang, B.; Huang, X. RNA: A Reject Neighbors Algorithm for Influence Maximization in Complex Networks. Mathematics 2020, 8, 1313. https://doi.org/10.3390/math8081313