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
PDF (2 MB)
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.

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[10]
S. B. Seidman, Network structure and minimum degree, Social Networks, vol. 5, no. 3, pp. 269–287, 1983.
[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.
[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.
[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.
[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.
[15]
V. Batagelj and M. Zaversnik, An o(m) algorithm for cores decomposition of networks, arXiv preprint arXiv: cs/0310049, 2003.
[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.
[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.
[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.
[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.
[20]
J. Wang and J. Cheng, Truss decomposition in massive networks, Proc. VLDB Endow., vol. 5, no. 9, pp. 812–823, 2012.
[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.
[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.
[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.
[24]
D. S. Hochbaum, Approximating clique and biclique problems, Journal of Algorithms, vol. 29, no. 1, pp. 174–200, 1998.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[34]
D. J. Watts and S. H. Strogatz, Collective dynamics of small world networks, Nature, vol. 393, pp. 440–442, 1998.
[35]
D. E. Knuth, Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition. Boston, MA, USA: Addison Wesley, 1997.
Tsinghua Science and Technology
Pages 292-309
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

582

Views

75

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