[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Anchored coreness: efficient reinforcement of social networks

  • Special Issue Paper
  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

The stability of a social network has been widely studied as an important indicator for both the network holders and the participants. Existing works on reinforcing networks focus on a local view, e.g., the anchored \(k\)-core problem aims to enlarge the size of the \(k\)-core with a fixed input k. Nevertheless, it is more promising to reinforce a social network in a global manner: considering the engagement of every user (vertex) in the network. Since the coreness of a user has been validated as the “best practice” for capturing user engagement, we propose and study the anchored coreness problem in this paper: anchoring a small number of vertices to maximize the coreness gain (the total increment of coreness) of all the vertices in the network. We prove the problem is NP-hard and show it is more challenging than the existing local-view problems. An efficient greedy algorithm is proposed with novel techniques on pruning search space and reusing the intermediate results. The algorithm is also extended to distributed environment with a novel graph partition strategy to ensure the computing independency of each machine. Extensive experiments on real-life data demonstrate that our model is effective for reinforcing social networks and our algorithms are efficient.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25

Similar content being viewed by others

References

  1. MPICH. https://www.mpich.org/

  2. OpenMP. https://www.openmp.org/

  3. Abello, J., Resende, M.G.C., Sudarsky, S.: Massive quasi-clique detection. In: LATIN, pp. 598–612 (2002)

  4. Aksu, H., Canim, M., Chang, Y., Korpeoglu, I., Ulusoy, Ö.: Distributed \(k\) -core view materialization and maintenance for large dynamic graphs. IEEE Trans. Knowl. Data Eng. 26(10), 2439–2452 (2014)

    Article  Google Scholar 

  5. Alvarez-Hamelin, J.I., Dall’Asta, L., Barrat, A., Vespignani, A.: Large scale networks fingerprinting and visualization using the k-core decomposition. In: NeurIPS, pp. 41–50 (2005)

  6. Aridhi, S., Brugnara, M., Montresor, A., Velegrakis, Y.: Distributed k-core decomposition and maintenance in large dynamic graphs. In: DEBS, pp. 161–168. ACM (2016)

  7. Bader, G.D., Hogue, C.W.V.: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinform. 4, 2 (2003)

    Article  Google Scholar 

  8. Batagelj, V., Zaversnik, M.: An o(m) algorithm for cores decomposition of networks. arXiv:cs.DS/0310049 (2003)

  9. Bhawalkar, K., Kleinberg, J.M., Lewi, K., Roughgarden, T., Sharma, A.: Preventing unraveling in social networks: the anchored k-core problem. In: ICALP, pp. 440–451 (2012)

  10. Bhawalkar, K., Kleinberg, J.M., Lewi, K., Roughgarden, T., Sharma, A.: Preventing unraveling in social networks: the anchored k-core problem. SIAM J. Discrete Math. 29(3), 1452–1475 (2015)

    Article  MathSciNet  Google Scholar 

  11. Blanco, M.P., Low, T.M., Kim, K.: Exploration of fine-grained parallelism for load balancing eager k-truss on GPU and CPU. In: HPEC, pp. 1–7. IEEE (2019)

  12. Bola, M., Sabel, B.A.: Dynamic reorganization of brain functional networks during cognition. NeuroImage 114, 398–413 (2015)

    Article  Google Scholar 

  13. Bonchi, F., Khan, A., Severini, L.: Distance-generalized core decomposition. In: SIGMOD, pp. 1006–1023 (2019)

  14. Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph (algorithm 457). Commun. ACM 16(9), 575–576 (1973)

    Article  Google Scholar 

  15. Carmi, S., Havlin, S., Kirkpatrick, S., Shavitt, Y., Shir, E.: A model of internet topology using k-shell decomposition. Proc. Natl. Acad. Sci. 104(27), 11150–11154 (2007)

    Article  Google Scholar 

  16. Chan, T.H., Sozio, M., Sun, B.: Distributed approximate k-core decomposition and min-max edge orientation: breaking the diameter barrier. In: IPDPS, pp. 345–354. IEEE (2019)

  17. Chang, L., Yu, J.X., Qin, L., Lin, X., Liu, C., Liang, W.: Efficiently computing k-edge connected components via graph decomposition. In: SIGMOD, pp. 205–216 (2013)

  18. Cheng, J., Ke, Y., Chu, S., Özsu, M.T.: Efficient core decomposition in massive networks. In: ICDE, pp. 51–62 (2011)

  19. Cheng, J., Ke, Y., Fu, A.W., Yu, J.X., Zhu, L.: Finding maximal cliques in massive networks by h*-graph. In: SIGMOD, pp. 447–458 (2010)

  20. Chitnis, R., Fomin, F.V., Golovach, P.A.: Parameterized complexity of the anchored k-core problem for directed graphs. Inf. Comput. 247, 11–22 (2016)

    Article  MathSciNet  Google Scholar 

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

  22. Chwe, M.S.-Y.: Communication and coordination in social networks. Rev. Econ. Stud. 67(1), 1–16 (2000)

    Article  MathSciNet  Google Scholar 

  23. Cohen, J.: Trusses: cohesive subgraphs for social network analysis. Natl. Secur. Agency Tech. Rep. 16, 3.1 (2008)

    Google Scholar 

  24. Conte, A., Firmani, D., Patrignani, M., Torlone, R.: Shared-nothing distributed enumeration of 2-plexes. In: CIKM, pp. 2469–2472. ACM (2019)

  25. Conte, A., Matteis, T.D., Sensi, D.D., Grossi, R., Marino, A., Versari, L.: D2K: scalable community detection in massive networks via small-diameter k-plexes. In: SIGKDD, pp. 1272–1281. ACM (2018)

  26. Das, A., Sanei-Mehri, S., Tirthapura, S.: Shared-memory parallel maximal clique enumeration from static and dynamic graphs. ACM Trans. Parallel Comput. 7(1), 5:1-5:28 (2020)

    Article  Google Scholar 

  27. Dourisboure, Y., Geraci, F., Pellegrini, M.: Extraction and classification of dense implicit communities in the web graph. TWEB 3(2), 7:1-7:36 (2009)

    Article  Google Scholar 

  28. Esfandiari, H., Lattanzi, S., Mirrokni, V.S.: Parallel and streaming algorithms for k-core decomposition. In: ICML, Volume 80 of Proceedings of Machine Learning Research, pp. 1396–1405. PMLR (2018)

  29. Fang, Y., Cheng, R., Li, X., Luo, S., Hu, J.: Effective community search over large spatial graphs. PVLDB 10(6), 709–720 (2017)

    Google Scholar 

  30. Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)

    Article  MathSciNet  Google Scholar 

  31. García, D., Mavrodiev, P., Schweitzer, F.: Social resilience in online communities: the autopsy of friendster. In: Conference on online social networks, pp. 39–50 (2013)

  32. Giatsidis, C., Malliaros, F.D., Thilikos, D.M., Vazirgiannis, M.: Corecluster: A degeneracy based graph clustering framework. In: AAAI, pp. 44–50 (2014)

  33. Hua, Q., Shi, Y., Yu, D., Jin, H., Yu, J., Cai, Z., Cheng, X., Chen, H.: Faster parallel core maintenance algorithms in dynamic graphs. IEEE Trans. Parallel Distrib. Syst. 31(6), 1287–1300 (2020)

    Article  Google Scholar 

  34. Huang, X., Cheng, H., Qin, L., Tian, W., Yu, J.X.: Querying k-truss community in large and dynamic graphs. In: SIGMOD, pp. 1311–1322 (2014)

  35. Jin, H., Wang, N., Yu, D., Hua, Q., Shi, X., Xie, X.: Core maintenance in dynamic graphs: a parallel approach based on matching. IEEE Trans. Parallel Distrib. Syst. 29(11), 2416–2428 (2018)

    Article  Google Scholar 

  36. Kabir, H., Madduri, K.: Parallel k-core decomposition on multicore platforms. In: IPDPS workshops, pp. 1482–1491. IEEE Computer Society (2017)

  37. Kabir, H., Madduri, K.: Parallel k-truss decomposition on multicore systems. In: HPEC, pp. 1–7. IEEE (2017)

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

  39. Khaouid, W., Barsky, M., Venkatesh, S., Thomo, A.: K-core decomposition of large networks on a single PC. PVLDB 9(1), 13–23 (2015)

    Google Scholar 

  40. Kitsak, M., Gallos, L.K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H.E., Makse, H.A.: Identification of influential spreaders in complex networks. Nat. Phys. 6(11), 888 (2010)

    Article  Google Scholar 

  41. Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data (2014)

  42. Li, R., Qin, L., Ye, F., Yu, J.X., Xiao, X., Xiao, N., Zheng, Z.: Skyline community search in multi-valued networks. In: SIGMOD, pp. 457–472 (2018)

  43. Lin, J.-H., Guo, Q., Dong, W.-Z., Tang, L.-Y., Liu, J.-G.: Identifying the node spreading influence with largest k-core values. Phys. Lett. A 378(45), 3279–3284 (2014)

    Article  Google Scholar 

  44. Linghu, Q., Zhang, F., Lin, X., Zhang, W., Zhang, Y.: Global reinforcement of social networks: the anchored coreness problem. In: SIGMOD, pp. 2211–2226. ACM (2020)

  45. Malliaros, F.D., Rossi, M.-E.G., Vazirgiannis, M.: Locating influential nodes in complex networks. Sci. Rep. 6, 19307 (2016)

    Article  Google Scholar 

  46. Malliaros, F.D., Vazirgiannis, M.: To stay or not to stay: modeling engagement dynamics in social graphs. In: CIKM, pp. 469–478 (2013)

  47. Mandal, A., Hasan, M.A.: A distributed k-core decomposition algorithm on spark. In: BigData, pp. 976–981. IEEE Computer Society (2017)

  48. Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417–427 (1983)

    Article  MathSciNet  Google Scholar 

  49. Montresor, A., Pellegrini, F.D., Miorandi, D.: Distributed k-core decomposition. IEEE Trans. Parallel Distrib. Syst. 24(2), 288–300 (2013)

    Article  Google Scholar 

  50. Morone, F., Del Ferraro, G., Makse, H.A.: The k-core as a predictor of structural collapse in mutualistic ecosystems. Nat. Phys. 15(1), 95 (2019)

    Article  Google Scholar 

  51. Pei, J., Jiang, D., Zhang, A.: On mining cross-graph quasi-cliques. In: SIGKDD, pp. 228–238 (2005)

  52. Seidman, S.B.: Network structure and minimum degree. Soc. Netw. 5(3), 269–287 (1983)

    Article  MathSciNet  Google Scholar 

  53. Seki, K., Nakamura, M.: The collapse of the friendster network started from the center of the core. In: ASONAM, pp. 477–484 (2016)

  54. Seki, K., Nakamura, M.: The mechanism of collapse of the Friendster network: what can we learn from the core structure of Friendster? Soc. Netw. Anal. Min. 7(1), 10:1-10:21 (2017)

    Article  Google Scholar 

  55. Shao, Y., Chen, L., Cui, B.: Efficient cohesive subgraphs detection in parallel. In: SIGMOD, pp. 613–624 (2014)

  56. Smith, S., Liu, X., Ahmed, N.K., Tom, A.S., Petrini, F., Karypis, G.: Truss decomposition on shared-memory parallel systems. In: HPEC, pp. 1–6. IEEE (2017)

  57. Tootoonchi, B., Srinivasan, V., Thomo, A.: Efficient implementation of anchored 2-core algorithm. In: ASONAM, pp. 1009–1016 (2017)

  58. Ugander, J., Backstrom, L., Marlow, C., Kleinberg, J.M.: Structural diversity in social contagion. Proc. Natl. Acad. Sci. U.S.A. 109(16), 5962–5966 (2012)

    Article  Google Scholar 

  59. Wang, J., Cheng, J.: Truss decomposition in massive networks. PVLDB 5(9), 812–823 (2012)

    Google Scholar 

  60. Wang, Z., Chen, Q., Hou, B., Suo, B., Li, Z., Pan, W., Ives, Z.G.: Parallelizing maximal clique and k-plex enumeration over graph data. J. Parallel Distrib. Comput. 106, 79–91 (2017)

    Article  Google Scholar 

  61. Wen, D., Qin, L., Zhang, Y., Lin, X., Yu, J.X.: I/O efficient core graph decomposition at web scale. In: ICDE, pp. 133–144 (2016)

  62. Wu, S., Sarma, A.D., Fabrikant, A., Lattanzi, S., Tomkins, A.: Arrival and departure dynamics in social networks. In: WSDM, pp. 233–242 (2013)

  63. Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: Cluster computing with working sets. In: HotCloud. USENIX Association (2010)

  64. Zhang, F., Yuan, L., Zhang, Y., Qin, L., Lin, X., Zhou, A.: Discovering strong communities with user engagement and tie strength. In: DASFAA, pp. 425–441 (2018)

  65. Zhang, F., Zhang, W., Zhang, Y., Qin, L., Lin, X.: OLAK: an efficient algorithm to prevent unraveling in social networks. PVLDB 10(6), 649–660 (2017)

    Google Scholar 

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

  67. Zhang, F., Zhang, Y., Qin, L., Zhang, W., Lin, X.: Efficiently reinforcing social networks over user engagement and tie strength. In: ICDE, pp. 557–568 (2018)

  68. Zhang, H., Zhao, H., Cai, W., Liu, J., Zhou, W.: Using the k-core decomposition to analyze the static structure of large-scale software systems. J. Supercomput. 53(2), 352–369 (2010)

    Article  Google Scholar 

  69. Zhao, F., Tung, A.K.H.: Large scale cohesive subgraphs discovery for social network visual analysis. PVLDB 6(2), 85–96 (2012)

    Google Scholar 

  70. Zhou, R., Liu, C., Yu, J.X., Liang, W., Chen, B., Li, J.: Finding maximal k-edge-connected subgraphs from a large graph. In: EDBT, pp. 480–491 (2012)

  71. Zhou, Y., Xu, J., Guo, Z., Xiao, M., Jin, Y.: Enumerating maximal k-plexes with worst-case time guarantee. In: AAAI, pp. 2442–2449. AAAI Press (2020)

  72. Zhou, Z., Zhang, F., Lin, X., Zhang, W., Chen, C.: K-core maximization: an edge addition approach. In: IJCAI, pp. 4867–4873 (2019)

Download references

Acknowledgements

Fan Zhang is supported by NSFC62002073. Xuemin Lin is supported by ARC DP200101338. Wenjie Zhang is supported by ARC DP210101393 and ARC DP200101116. Ying Zhang is supported by FT170100128 and ARC DP180103096.

Author information

Authors and Affiliations

  1. University of New South Wales, Sydney, Australia

    Qingyuan Linghu, Xuemin Lin & Wenjie Zhang

  2. Guangzhou University, Guangzhou, China

    Fan Zhang

  3. Centre for AI, University of Technology Sydney, Sydney, Australia

    Ying Zhang

Authors
  1. Qingyuan Linghu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xuemin Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wenjie Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ying Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fan Zhang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Linghu, Q., Zhang, F., Lin, X. et al. Anchored coreness: efficient reinforcement of social networks. The VLDB Journal 31, 227–252 (2022). https://doi.org/10.1007/s00778-021-00673-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00778-021-00673-6

Keywords

Search

Navigation