research-article

Critical Nodes Identification in Large Networks: The Inclined and Detached Models

Authors:

Xuemin LinAuthors Info & Claims

World Wide Web, Volume 25, Issue 3

Pages 1315 - 1341

https://doi.org/10.1007/s11280-022-01049-8

Published: 01 May 2022 Publication History

Abstract

In social networks, the departure of some users can lead to the dropout of others from the community in cascade. Therefore, the engagement of critical users can significantly influence the stability of a network. In the literature, the anchored/collapsed k-core problem is proposed, which aims to enlarge/collapse the community by anchoring/deleting certain nodes. While, in real social networks, nodes are usually associated with different preferences, such as close or conflict interest. Intuitively, a community will be more stable if more nodes share close interest and fewer of them carry conflict interest. However, most existing researches simply treat all users equally, and the inclination property is neglected. To fill the gap, in this paper, we propose two novel problems, named inclined anchored k-core (IAK) problem and minimum detached k-core (MDK) problem, to better characterize the real scenarios. We prove that both problems are NP-hard. To facilitate the computation, novel search strategies are proposed. Comprehensive experiments are conducted on 9 networks to demonstrate the effectiveness and efficiency of the proposed techniques.

References

[1]

Batagelj, V., Zaversnik, M.: An o(m) algorithm for cores decomposition of networks. CoRR (2003)

[2]

Bhawalkar K, Kleinberg J, Lewi K, Roughgarden T, and Sharma A Preventing unraveling in social networks: the anchored k-core problem SIAM Journal on Discrete Mathematics 2015 29 3 1452-1475

[3]

Burke, M., Marlow, C., Lento, T.: Feed me: motivating newcomer contribution in social network sites. In: SIGCHI, pp. 945–954 (2009)

[4]

Chen, C., Liu, X., Xu, S., Zhang, M., Wang, X., Lin, X.: Critical nodes identification in large networks: An inclination-based model. In: WISE, pp. 453–468 (2021)

[5]

Chen, C., Wu, Y., Sun, R., Wang, X.: Maximum signed

θ

-clique identification in large signed graphs. TKDE (2021)

[6]

Chen, C., Zhang, M., Sun, R., Wang, X., Zhu, W., Wang, X.: Locating pivotal connections: The k-truss minimization and maximization problems. WWW Journal pp. 1–28 (2021)

[7]

Chen, C., Zhu, Q., Sun, R., Wang, X., Wu, Y.: Edge manipulation approaches for k-core minimization: Metrics and analytics. TKDE (2021)

[8]

Chen, C., Zhu, Q., Wu, Y., Sun, R., Wang, X., Liu, X.: Efficient critical relationships identification in bipartite networks. WWW Journal (2021)

[9]

Chen, H., Conte, A., Grossi, R., Loukides, G., Pissis, S.P., Sweering, M.: On breaking truss-based communities. In: KDD, pp. 117–126 (2021)

[10]

Cheng, D., Chen, C., Wang, X., Xiang, S.: Efficient top-k vulnerable nodes detection in uncertain graphs. TKDE (2021)

[11]

Chitnis R, Fomin FV, and Golovach PA Parameterized complexity of the anchored k-core problem for directed graphs Information and Computation 2016 247 11-22

[12]

Chitnis, R.H., Fomin, F.V., Golovach, P.A.: Preventing unraveling in social networks gets harder. In: AAAI (2013)

[13]

Cohen, J.: Trusses: Cohesive subgraphs for social network analysis. National security agency technical report (2008)

[14]

He, J., Rong, J., Sun, L., Wang, H., Zhang, Y., Ma, J.: A framework for cardiac arrhythmia detection from IoT-based ECGs. World Wide Web 23(5), 2835–2850 (2020)

[15]

Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations, pp. 85–103. Springer (1972)

[16]

Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, and Makse HA Identification of influential spreaders in complex networks Nature physics 2010 6 11 888-893

[17]

Liu, K., Wang, S., Zhang, Y., Xing, C.: An efficient algorithm for the anchored k-core budget minimization problem. In: ICDE, pp. 1356–1367 (2021)

[18]

Medya, S., Ma, T., Silva, A., Singh, A.: A game theoretic approach for core resilience. In: IJCAI (2020)

[19]

Medya, S., Ma, T., Silva, A., Singh, A.: A game theoretic approach for k-core minimization. In: International Conference on Autonomous Agents and MultiAgent Systems (2020)

[20]

Seidman SB Network structure and minimum degree Social networks 1983 5 3 269-287

[21]

Sun, R., Chen, C., Wang, X., Wu, Y., Zhang, M., Liu, X.: The art of characterization in large networks: Finding the critical attributes. WWW Journal (2021)

[22]

Sun, R., Chen, C., Wang, X., Zhang, Y., Wang, X.: Stable community detection in signed social networks. TKDE (2020)

[23]

Sun, R., Zhu, Q., Chen, C., Wang, X., Zhang, Y., Wang, X.: Discovering cliques in signed networks based on balance theory. In: DASFAA (2020)

[24]

Tawhid, Md. N.A., Siuly S., Wang, K., Wang, H.: Data mining based artificial intelligent technique for identifying abnormalities from brain signal data: WISE, 198–206 (2021)

[25]

Ugander J, Backstrom L, Marlow C, and Kleinberg J Structural diversity in social contagion Proceedings of the National Academy of Sciences 2012 109 16 5962-5966

[26]

Vazquez A, Flammini A, Maritan A, and Vespignani A Global protein function prediction from protein-protein interaction networks Nature biotechnology 2003 21 6 697-700

[27]

Wang, X., Zhang, Y., Zhang, W., Lin, X., Chen, C.: Bring order into the samples: A novel scalable method for influence maximization. IEEE Transactions on Knowledge and Data Engineering 29(2), 243–256 (2016)

[28]

Zhang F, Zhang W, Zhang Y, Qin L, and Lin X Olak: an efficient algorithm to prevent unraveling in social networks PVLDB 2017 10 6 649-660

[29]

Zhang, F., Zhang, Y., Qin, L., Zhang, W., Lin, X.: Finding critical users for social network engagement: The collapsed k-core problem. In: AAAI (2017)

[30]

Zhao, J., Sun, R., Zhu, Q., Wang, X., Chen, C.: Community identification in signed networks: a k-truss based model. In: CIKM (2020)

[31]

Zhu, Q., Zheng, J., Yang, H., Chen, C., Wang, X., Zhang, Y.: Hurricane in bipartite graphs: The lethal nodes of butterflies. In: SSDBM (2020)

[32]

Zhu, W., Chen, C., Wang, X., Lin, X.: K-core minimization: An edge manipulation approach. In: CIKM, pp. 1667–1670 (2018)

[33]

Zhu, W., Zhang, M., Chen, C., Wang, X., Zhang, F., Lin, X.: Pivotal relationship identification: The k-truss minimization problem. In: IJCAI (2019)

Cited By

Xiang FWang JWu YWang XChen CZhang Y(2024)Rumor blocking with pertinence set in large graphsWorld Wide Web10.1007/s11280-024-01235-w27:1Online publication date: 20-Jan-2024
https://dl.acm.org/doi/10.1007/s11280-024-01235-w
Zhao MZhai YLi D(2024)Assessing edge importance in social networks: an importance indicator based on the -sup structureThe Journal of Supercomputing10.1007/s11227-024-06239-x80:13(19796-19823)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11227-024-06239-x
Li XYang ZHao KShu XCao XZhang W(2024)Distributed Hop-Constrained s-t Simple Path Enumeration in Labelled GraphsDatabases Theory and Applications10.1007/978-981-96-1242-0_20(265-278)Online publication date: 17-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-1242-0_20
Show More Cited By

Index Terms

Critical Nodes Identification in Large Networks: The Inclined and Detached Models

Index terms have been assigned to the content through auto-classification.

Recommendations

Critical Nodes Identification in Large Networks: An Inclination-Based Model
Web Information Systems Engineering – WISE 2021
Abstract
In social networks, the departure of some users can lead to the drop-out of others in cascade. Therefore, the engagement of critical users can significantly influence the stability of a network. In the literature, the anchored k-core problem is ...
Approximation algorithms for clique transversals on some graph classes

Given a graph G = ( V , E ) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique ...
Restrained condition on double Roman dominating functions
Abstract
We continue the study of restrained double Roman domination in graphs. For a graph G = ( V ( G ) , E ( G ) ), a double Roman dominating function f is called a restrained double Roman dominating function (RDRD function) if the subgraph ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image World Wide Web

World Wide Web Volume 25, Issue 3

May 2022

438 pages

ISSN:1386-145X

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2022.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 May 2022

Accepted: 18 March 2022

Revision received: 10 January 2022

Received: 10 January 2022

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xiang FWang JWu YWang XChen CZhang Y(2024)Rumor blocking with pertinence set in large graphsWorld Wide Web10.1007/s11280-024-01235-w27:1Online publication date: 20-Jan-2024
https://dl.acm.org/doi/10.1007/s11280-024-01235-w
Zhao MZhai YLi D(2024)Assessing edge importance in social networks: an importance indicator based on the -sup structureThe Journal of Supercomputing10.1007/s11227-024-06239-x80:13(19796-19823)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11227-024-06239-x
Li XYang ZHao KShu XCao XZhang W(2024)Distributed Hop-Constrained s-t Simple Path Enumeration in Labelled GraphsDatabases Theory and Applications10.1007/978-981-96-1242-0_20(265-278)Online publication date: 17-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-1242-0_20
Luo QYu DCai ZZheng YCheng XLin X(2023)Core maintenance for hypergraph streamsWorld Wide Web10.1007/s11280-023-01196-626:5(3709-3733)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1007/s11280-023-01196-6
Li XHao KYang ZCao XZhang WYuan LLin X(2022)Hop-Constrained s-t Simple Path Enumeration in Billion-Scale Labelled GraphsWeb Information Systems Engineering – WISE 202210.1007/978-3-031-20891-1_5(49-64)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-20891-1_5

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents