Core Decomposition and Maintenance in Bipartite Graphs

Dongxiao Yu; Lifang Zhang; Qi Luo; Xiuzhen Cheng; Zhipeng Cai

doi:10.26599/TST.2021.9010091

Tsinghua Science and Technology 2023, 28(2): 292-309 https://doi.org/10.26599/TST.2021.9010091

Open Access | Issue | Published: 29 September 2022

Core Decomposition and Maintenance in Bipartite Graphs

Show Author's Information Hide Author's Information Dongxiao Yu^¹, Lifang Zhang^¹, Qi Luo^¹(

), Xiuzhen Cheng^¹, Zhipeng Cai^²

1School of Computer Science and Technology, Shandong University, Qingdao 266237, China

2Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA

Keywords:

core decomposition, core maintenance, bipartite graph, dense subgraph mining

Cite this article:

Yu D, Zhang L, Luo Q, et al. Core Decomposition and Maintenance in Bipartite Graphs. Tsinghua Science and Technology, 2023, 28(2): 292-309. https://doi.org/10.26599/TST.2021.9010091

Download citation

EndNote(RIS)

BibTeX

475

Views

Downloads

Citations

Crossref

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining. In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs, only very few indexes are proposed for the same in bipartite graphs. In this work, we present the index called $α (β)$ -core number on vertices, which reflects the maximal cohesive and dense subgraph a vertex can be in, to help enumerate the $(α, β)$ -cores, a commonly used dense structure in bipartite graphs. To address the problem of extremely high time and space cost for enumerating the $(α, β)$ -cores, we first present a linear time and space algorithm for computing the $α (β)$ -core numbers of vertices. We further propose core maintenance algorithms, to update the core numbers of vertices when a graph changes by avoiding recalculations. Experimental results on different real-world and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.

Full text

Abstract

Full text

Outline

About this article

Core Decomposition and Maintenance in Bipartite Graphs

Show Author's information Hide Author's Information Dongxiao Yu^¹, Lifang Zhang^¹, Qi Luo^¹(

), Xiuzhen Cheng^¹, Zhipeng Cai^²

1School of Computer Science and Technology, Shandong University, Qingdao 266237, China

2Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA

Abstract

Keywords: core decomposition, core maintenance, bipartite graph, dense subgraph mining

References(35)

[1]

A. Beutel, W. Xu, V. Guruswami, C. Palow, and C. Faloutsos, Copycatch: Stopping group attacks by spotting lockstep behavior in social networks, in Proc. 22^nd International Conference on World Wide Web, Rio de Janeiro, Brazil, 2013, pp. 119–130.

DOI Google Scholar

[2]

M. Kaytoue, S. O. Kuznetsov, A. Napoli, and S. Duplessis, Mining gene expression data with pattern structures in formal concept analysis, Inf. Sci., vol. 181, no. 10, pp. 1989–2001, 2011.

DOI Google Scholar

[3]

J. Wang, A. P. de Vries, and M. J. T. Reinders, Unifying user-based and item-based collaborative filtering approaches by similarity fusion, in Proc. 29^th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, WA, USA, 2006, pp. 501–508.

DOI Google Scholar

[4]

D. Ding, H. Li, Z. Huang, and N. Mamoulis, Efficient fault-tolerant group recommendation using alpha-beta-core, in Proc. 2017 ACM on Conference on Information and Knowledge Management, Singapore, 2017, pp. 2047–2050.

DOI Google Scholar

[5]

Z. Cai, Z. He, X. Guan, and Y. Li, Collective data-sanitization for preventing sensitive information inference attacks in social networks, IEEE Trans. Dependable Secur. Comput., vol. 15, no. 4, pp. 577–590, 2018.

Google Scholar

[6]

K. Li, G. Lu, G. Luo, and Z. Cai, Seed-free graph de-anonymiztiation with adversarial learning, in Proc. 29^th ACM International Conference on Information & Knowledge Management, Virtual Event, Ireland, 2020, pp. 745–754.

DOI Google Scholar

[7]

K. Li, G. Luo, Y. Ye, W. Li, S. Ji, and Z. Cai, Adversarial privacy-preserving graph embedding against inference attack, IEEE Internet Things J., vol. 8, no. 8, pp. 6904–6915, 2021.

DOI Google Scholar

[8]

K. Xu, R. Williams, S. H. Hong, Q. Liu, and J. Zhang, Semi-bipartite graph visualization for gene ontology networks, in Proc. 17^th international conference on Graph Drawing, Chicago, IL, USA, 2009, pp. 244–255.

DOI Google Scholar

[9]

B. Liu, L. Yuan, X. Lin, L. Qin, W. Zhang, and J. Zhou, Efficient (α, β)-core computation in bipartite graphs, VLDB J., vol. 29, no. 5, pp. 1075–1099, 2020.

DOI Google Scholar

[10]

S. B. Seidman, Network structure and minimum degree, Social Networks, vol. 5, no. 3, pp. 269–287, 1983.

DOI Google Scholar

[11]

Q. -S. Hua, Y. Shi, D. Yu, H. Jin, J. Yu, Z. Cai, X. Cheng, and H. Chen, Faster parallel core maintenance algorithms in dynamic graphs, IEEE Trans. Parallel Distributed Syst., vol. 31, no. 6, pp. 1287–1300, 2020.

DOI Google Scholar

[12]

Y. Zhang, B. Wu, Y. Liu, and J. Lv, Local community detection based on network motifs, Tsinghua Science and Technology, vol. 24, no. 6, pp. 716–727, 2019.

DOI Google Scholar

[13]

L. Yu, B. Wu, and B. Wang. LBLP: Link-clustering-based approach for overlapping community detection, Tsinghua Science and Technology, vol. 4, pp. 387–397, 2013.

DOI Google Scholar

[14]

U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy, Approximating clique is almost NP-complete (preliminary version), in Proc. 32^nd Annual Symposium on Foundations of Computer Science, San Juan, PR, USA, 1991, pp. 2–12.

Google Scholar

[15]

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

Google Scholar

[16]

Q. Luo, D. Yu, F. Li, Z. Dou, Z. Cai, J. Yu, and X. Cheng, Distributed core decomposition in probabilistic graphs, in Proc. 8^th International Conference on Computational Data and Social Networks, Ho Chi Minh City, Vietnam, 2019, pp. 16–32.

DOI Google Scholar

[17]

D. Yu, L. Zhang, Q. Luo, X. Cheng, J. Yu, and Z. Cai, Fast skyline community search in multi-valued networks, Big Data Mining Analytics, vol. 3, no. 3, pp. 171–180, 2020.

DOI Google Scholar

[18]

P. Chen, C. Chou, and M. Chen, Distributed algorithms for k-truss decomposition, in Proc. 2014 IEEE International Conference on Big Data, Washington, DC, USA, 2014, pp. 471–480.

DOI Google Scholar

[19]

Q. Luo, D. Yu, X. Cheng, Z. Cai, J. Yu, and W. Lv, Batch processing for truss maintenance in large dynamic graphs, IEEE Trans. Comput. Soc. Syst., vol. 7, no. 6, pp. 1435–1446, 2020.

DOI Google Scholar

[20]

J. Wang and J. Cheng, Truss decomposition in massive networks, Proc. VLDB Endow., vol. 5, no. 9, pp. 812–823, 2012.

DOI Google Scholar

[21]

B. Balasundaram, S. Butenko, and I. V. Hicks, Clique relaxations in social network analysis: The maximum k-plex problem, Oper. Res., vol. 59, no. 1, pp. 133–142, 2011.

DOI Google Scholar

[22]

M. Bentert, A. -S. Himmel, H. Molter, M. Morik, R. Niedermeier, and R. Saitenmacher, Listing all maximal k-plexes in temporal graphs, in Proc. 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Barcelona, Spain, 2018, pp. 41–46.

DOI Google Scholar

[23]

A. Ahmed, V. Batagelj, X. Fu, S. Hong, D. Merrick, and A. Mrvar, Visualisation and analysis of the internet movie database, in Proc. 2007 6^th International Asia-Pacific Symposium on Visualization, Sydney, Australia, 2007, pp.17–24.

DOI Google Scholar

[24]

D. S. Hochbaum, Approximating clique and biclique problems, Journal of Algorithms, vol. 29, no. 1, pp. 174–200, 1998.

DOI Google Scholar

[25]

K. Sim, J. Li, V. Gopalkrishnan, and G. Liu, Mining maximal quasi-bicliques to co-cluster stocks and financial ratios for value investment, in Proc. 6^th IEEE International Conference on Data Mining (ICDM 2006), Hong Kong, China, 2006, pp. 1059–1063.

DOI Google Scholar

[26]

A. E. Sarıyüce, B. Gedik, G. Jacques-Silva, K. -L. Wu, and Ü. V. Çatalyürek, Incremental k-core decomposition: Algorithms and evaluation, VLDB J., vol. 25, no. 3, pp. 425–447, 2016.

DOI Google Scholar

[27]

N. Wang, D. Yu, H. Jin, C. Qian, X. Xie, and Q. -S. Hua, Parallel algorithms for core maintenance in dynamic graphs, arXiv preprint arXiv: 1612.09368, 2016.

Google Scholar

[28]

H. Jin, N. Wang, D. Yu, Q. -S. Hua, X. Shi, and X. Xie, Core maintenance in dynamic graphs: A parallel approach based on matching, IEEE Trans. Parallel Distributed Syst., vol. 29, no. 11, pp. 2416–2428, 2018.

DOI Google Scholar

[29]

A. E. Sariyüce, C. Seshadhri, A. Pinar, and Ü. V. Catalyurek, Finding the hierarchy of dense subgraphs using nucleus decompositions, in Proc. 24^th International Conference on World Wide Web, Florence, Italy, 2015, pp. 927–937.

DOI Google Scholar

[30]

H. Aksu, M. Canim, Y. -C. Chang, I. Korpeoglu, and Ö. Ulusoy, Distributed k-core view materialization and maintenance for large dynamic graphs, IEEE Trans. Knowl. Data Eng., vol. 26, no. 10, pp. 2439–2452, 2014.

DOI Google Scholar

[31]

S. Aridhi, M. Brugnara, A. Montresor, and Y. Velegrakis, Distributed k-core decomposition and maintenance in large dynamic graphs, in Proc. 10^th ACM International Conference on Distributed and Event-Based Systems, Irvine, CA, USA, 2016, pp. 161–168.

DOI Google Scholar

[32]

W. Zhou, H. Huang, Q. -S. Hua, D. Yu, H. Jin, and X. Fu, Core decomposition and maintenance in weighted graph, World Wide Web, vol. 24, no. 2, pp. 541–561, 2021.

DOI Google Scholar

[33]

Q. Luo, D. Yu, Z. Cai, X. Lin, and X. Cheng, Hypercore maintenance in dynamic hypergraphs, in Proc. 2021 IEEE 37^th International Conference on Data Engineering (ICDE), Chania, Greece, 2021, pp. 2051–2056.

DOI Google Scholar

[34]

D. J. Watts and S. H. Strogatz, Collective dynamics of small world networks, Nature, vol. 393, pp. 440–442, 1998.

DOI Google Scholar

[35]

D. E. Knuth, Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3^rd Edition. Boston, MA, USA: Addison Wesley, 1997.

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 12 October 2021

Revised: 16 November 2021

Accepted: 19 November 2021

Published: 29 September 2022

Issue date: April 2023

Copyright

Acknowledgements

This work was supported by the National Key Research and Development Program of China (No. 2019YFB2102600), the National Natural Science Foundation of China (Nos. 62122042 and 61971269), and the Blockchain Core Technology Strategic Research Program of Ministry of Education of China (No. 2020KJ010301) fund.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).