AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Core Decomposition and Maintenance in Bipartite Graphs

School of Computer Science and Technology, Shandong University, Qingdao 266237, China
Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA
Show Author Information

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.

Keywords

core decompositioncore maintenancebipartite graphdense subgraph mining

References

[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. 22nd International Conference on World Wide Web, Rio de Janeiro, Brazil, 2013, pp. 119–130.
Crossref 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.
Crossref 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. 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, WA, USA, 2006, pp. 501–508.
Crossref 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.
Crossref 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. 29th ACM International Conference on Information & Knowledge Management, Virtual Event, Ireland, 2020, pp. 745–754.
Crossref 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.
Crossref 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. 17th international conference on Graph Drawing, Chicago, IL, USA, 2009, pp. 244–255.
Crossref 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.
Crossref Google Scholar
[10]
S. B. Seidman, Network structure and minimum degree, Social Networks, vol. 5, no. 3, pp. 269–287, 1983.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[14]
U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy, Approximating clique is almost NP-complete (preliminary version), in Proc. 32nd 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. 8th International Conference on Computational Data and Social Networks, Ho Chi Minh City, Vietnam, 2019, pp. 16–32.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[20]
J. Wang and J. Cheng, Truss decomposition in massive networks, Proc. VLDB Endow., vol. 5, no. 9, pp. 812–823, 2012.
Crossref 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.
Crossref 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.
Crossref 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 6th International Asia-Pacific Symposium on Visualization, Sydney, Australia, 2007, pp.17–24.
Crossref Google Scholar
[24]
D. S. Hochbaum, Approximating clique and biclique problems, Journal of Algorithms, vol. 29, no. 1, pp. 174–200, 1998.
Crossref 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. 6th IEEE International Conference on Data Mining (ICDM 2006), Hong Kong, China, 2006, pp. 1059–1063.
Crossref 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.
Crossref 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.
Crossref 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. 24th International Conference on World Wide Web, Florence, Italy, 2015, pp. 927–937.
Crossref 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.
Crossref Google Scholar
[31]
S. Aridhi, M. Brugnara, A. Montresor, and Y. Velegrakis, Distributed k-core decomposition and maintenance in large dynamic graphs, in Proc. 10th ACM International Conference on Distributed and Event-Based Systems, Irvine, CA, USA, 2016, pp. 161–168.
Crossref 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.
Crossref Google Scholar
[33]
Q. Luo, D. Yu, Z. Cai, X. Lin, and X. Cheng, Hypercore maintenance in dynamic hypergraphs, in Proc. 2021 IEEE 37th International Conference on Data Engineering (ICDE), Chania, Greece, 2021, pp. 2051–2056.
Crossref Google Scholar
[34]
D. J. Watts and S. H. Strogatz, Collective dynamics of small world networks, Nature, vol. 393, pp. 440–442, 1998.
Crossref Google Scholar
[35]
D. E. Knuth, Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition. Boston, MA, USA: Addison Wesley, 1997.
Tsinghua Science and Technology
Volume 28 Issue 2,
April 2023
Pages 292-309
DOI: 10.26599/TST.2021.9010091
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

728

Views

81

Downloads

1

Crossref

0

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 12 October 2021
Revised: 16 November 2021
Accepted: 19 November 2021
Published: 29 September 2022
© The author(s) 2023.

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/).
Return