基于冗余感知极大团中心性的复杂网络关键节点识别

Identification of key nodes in complex networks via redundancy-aware maximal clique centrality

摘要

针对复杂网络多源传播中现有方法易导致影响力重叠的问题，本文提出了基于冗余感知极大团中心性的复杂网络关键节点识别方法。该方法以极大团为基础计算单元，精准量化节点在跨越低约束极大团时的高阶桥接价值；引入 Katz 中心性作为全局惩罚项，以寻找拓扑分布离散且互补的次核心枢纽，实现动力学去冗余。参数分析实验揭示了去冗余强度与网络结构的内在关联。6 个真实世界网络上的易感−感染−恢复动力学仿真实验表明，该方法有效克服了局部传播内耗，在不同干预比例下均实现了最优的标准化稳态感染规模。单调性指数与平均最短路径长度分析结果证实，该方法具备极高的节点排序分辨率和空间离散度。

Abstract

To address the issue of influence overlap commonly caused by existing methods in multi-source spreading on complex networks, this paper proposes a redundancy-aware maximal clique centrality method for key node identification in complex networks. Taking maximal cliques as the fundamental computational unit, the proposed method accurately quantifies the higher-order bridging value of nodes as they span low-constraint maximal cliques. Furthermore, Katz centrality is introduced as a global penalty term to identify topologically dispersed and complementary sub-core hubs, thereby achieving dynamical de-redundancy. Parameter analysis experiments reveal the intrinsic correlation between de-redundancy intensity and network structure. Susceptible-Infected-Recovered spreading dynamics simulations conducted on six real-world networks demonstrate that this method effectively overcomes local spreading interference, achieving the optimal standardized steady-state infection scale across various intervention ratios. Numerical results, supported by analyses of the monotonicity index and average shortest path length, confirm that the proposed method exhibits exceptionally high node-ranking resolution and spatial dispersion.

关键词

冗余感知 / 极大团 / 复杂网络 / 关键节点识别

Key words

redundancy-aware / maximal clique / complex networks / key node identification

作者贡献声明

孙培耀提出并设计本研究，完成数值模拟，开展理论分析，解读研究结果，并撰写论文。张靖文负责数据处理与分析，参与理论分析。王思哲负责数据处理与分析。王浩华提供理论和论文指导与论文修改，并提供经费支持。

AI使用声明

本文未使用人工智能（AI）协助撰写。

利益冲突声明

作者声明，其不存在已知的可能影响本论文所报告工作的竞争性经济利益或个人关系。

伦理声明

不适用：本文不涉及人类或动物的生物学研究。

数据可用性

支持论文结论所需的所有数据均已包含在稿件和/或电子补充材料中。如需获取与本文相关的其他数据，可向通信作者提出申请。

参考文献

[1] Strogatz S H . Exploring complex networks[J]. Nature， 2001， 410(6825)： 268-276.

[2] Yeung C M A， Liccardi I， Lu K H， et al. Decentralization：the future of online social networking[C]// Linking the World’s Information： Essays on Tim Berners—lee’s Invention of the World Wide Web. New York: Association for Computing Machinery， 2023： 187-199. DOI: 10.1145/3591366.3591383.

[3] Gosak M， Markovič R， Dolenšek J， et al. Network science of biological systems at different scales：a review[J]. Physics of Life Reviews， 2018， 24： 118-135.

[4] Zanin M， Sun X， Wandelt S . Studying the topology of transportation systems through complex networks：handle with care[J]. Journal of Advanced Transportation， 2018， 2018(1)： 3156137.

[5] Chen D X， Chen J W， Zhang X Y， et al. Critical nodes identification in complex networks：a survey[J]. Complex Engineering Systems， 2025， 5(3)： 11.

[6] Pastor—Satorras R， Castellano C， Van Mieghem P， et al. Epidemic processes in complex networks[J]. Reviews of Modern Physics， 2015， 87(3)： 925-979.

[7] Zhao L J， Qiu X Y， Wang X L， et al. Rumor spreading model considering forgetting and remembering mechanisms in inhomogeneous networks[J]. Physica A：Statistical Mechanics and its Applications， 2013， 392(4)： 987-994.

[8] Freeman L C . Centrality in social networks conceptual clarification[J]. Social Networks， 1978， 1(3)： 215-239.

[9] Newman M E J . A measure of betweenness centrality based on random walks[J]. Social Networks， 2005， 27(1)： 39-54.

[10] Kitsak M， Gallos L K， Havlin S， et al. Identification of influential spreaders in complex networks[J]. Nature Physics， 2010， 6(11)： 888-893.

[11] Zhang J X， Chen D B， Dong Q， et al. Identifying a set of influential spreaders in complex networks[J]. Scientific Reports， 2016， 6： 27823.

[12] Liu P F， Li L J， Fang S Y， et al. Identifying influential nodes in social networks：a voting approach[J]. Chaos，Solitons & Fractals， 2021， 152： 111309. DOI: 10.1016/j.chaos.2021.111309.

[13] Guo C G， Yang L W， Chen X， et al. Influential nodes identification in complex networks via information entropy[J]. Entropy， 2020， 22(2)： 242.

[14] Zhong L F， Gao X Y， Zhao L， et al. Identifying key nodes in complex networks based on an improved gravity model[J]. Frontiers in Physics， 2023， 11： 1239660.

[15] Fan C J， Zeng L， Sun Y Z， et al. Finding key players in complex networks through deep reinforcement learning[J]. Nature Machine Intelligence， 2020， 2(6)： 317-324.

[16] Majhi S， Perc M， Ghosh D . Dynamics on higher—order networks：a review[J]. Journal of the Royal Society Interface， 2022， 19(188)： 20220043.

[17] Colizza V， Flammini A， Serranno M A， et al. Detecting rich—club ordering in complex networks[J]. Nature Physics， 2006， 2(2)： 110-115.

[18] Kempe D， Kleinberg J， Tardos É . Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington：ACM， 2003： 137-146. DOI: 10.1145/956750.956769.

[19] Katz L. A new status index derived from sociometric analysis[J]. Psychometrika， 1953， 18(1)： 39-43.

[20] Sabidussi G . The centrality index of a graph[J]. Psychometrika， 1966， 31(4)： 581-603.

[21] Bron C， Kerbosch J . Algorithm 457：finding all cliques of an undirected graph[J]. Communications of the ACM， 1973， 16(9)： 575-577.

[22] Lusseau D， Schneider K， Boisseau O J， et al. The bottlenose dolphin community of doubtful sound features a large proportion of long—lasting associations： can geographic isolation explain this unique trait?[J]. Behavioral Ecology and Sociobiology， 2003， 54(4)： 396-405.

[23] Knuth D E . The Stanford GraphBase：A platform for combinatorial computing[M]. New York：Association for Computing Machinery， 1993. DOI: 10.1145/164984.

[24] Newman M E J . Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E， 2006， 74(3)： 036104.

[25] Guimerà R， Danon L， Díaz—Guilera A， et al. Self—similar community structure in a network of human interactions[J]. Physical Review E， 2003， 68(6)： 065103.

[26] Kunegis J . KONECT：the koblenz network collection[C]// Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro：ACM， 2013： 1343-1350. DOI: 10.1145/2487788.2488173.

[27] Rozemberczki B， Sarkar R . Characteristic functions on graphs：birds of a feather，from statistical descriptors to parametric models[C]// Proceedings of the 29th ACM International Conference on Information & Knowledge Management. New York: Association for Computing Machinery， 2020： 1325-1334. DOI: 10.1145/3340531.3411866.

[28] Keeling M J， Eames K T D . Networks and epidemic models[J]. Journal of the Royal Society Interface， 2005， 2(4)： 295-307.

[29] Castellano C， Pastor—Satorras R . Thresholds for epidemic spreading in networks[J]. Physical Review Letters， 2010， 105(21)： 218701.

[30] Berahmand K， Bouyer A， Samdi N . A new centrality measure based on the negative and positive effects of clustering coefficient for identifying influential spreaders in complex networks[J]. Chaos， Solitons & Fractals， 2018， 110： 41-54. DOI: 10.1016/j.chaos.2018.03.014.

[31] Bae J， Kim S . Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A：Statistical Mechanics and its Applications， 2014， 395： 549-559.

[32] Zhao Z L， Li D， Sun Y， et al. Ranking influential spreaders based on both node k—shell and structural hole[J]. Knowledge—Based Systems， 2023， 260： 110163.