Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (11): 95-102.doi: 10.11896/jsjkx.231000130

• Database & Big Data & Data Science • Previous Articles     Next Articles

Distance-generalized Based (α,β)-core Decomposition on Bipartite Graphs

ZHANG Yihao1, HUA Zhengyu1, YUAN Long1, ZHANG Fan2, WANG Kai3, CHEN Zi4   

  1. 1 School of Computer Science and Technology,Nanjing University of Science and Technology,Nanjing 210094,China
    2 School of Cybersecurity,Guangzhou University,Guangzhou 510555,China
    3 Antai College of Economics & Management,Shanghai Jiao Tong University,Shanghai 200030,China
    4 College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
  • Received:2023-10-20 Revised:2024-03-11 Online:2024-11-15 Published:2024-11-06
  • About author:ZHANG Yihao,born in 1999,postgra-duate.His main research interests include graph data management and ana-lysis,and so on.
    YUAN Long,born in 1988,Ph.D,professor,is a senior member of CCF(No.B0267S).His main research interests include graph data management and analysis,and so on.
  • Supported by:
    National Key Research and Development Program of China(2022YFF0712100),Key Laboratory Program of Information Systems Engineering(WDZC20205250411) and Young Scientists Fund of the National Natural Science Foundation of China(NSFC61902184).

PDF (PC)

230

Abstract: (α,β)-core decomposition is a fundamental problem in graph analysis,and has been widely adopted for e-commerce fraud detection and interest group recommendation.Nevertheless,(α,β)-core model only considers the distance-1 neighborhood,which makes it unable to provide more fine-grained structure information.Motivated by this,(α,β,h)-core model is proposed in this paper,which requires the vertices in one/another part has at least α other vertices at distance not greater than h within the subgraph.Due to the distance-h neighborhoods being considered,the new model can identify more fine-grained structure information as verified in our experiments,which also makes the corresponding (α,β,h)-core decomposition challenging.To address this problem,an efficient algorithm based on computation-sharing strategy is proposed and time complexity is analyzed accordingly.As obtaining neighbors within distance h is time-consuming,a lower bound related to (α,β,h)-core is designed to avoid unnecessary distance-h neighbors computation to further improve the computational efficiency.Experimental results on eight real graphs de-monstrate the effectiveness of the proposed model and efficiency of its algorithm.

Key words: Bipartitegraphs, (α, β, h)-core decomposition, Efficient algorithm

CLC Number: 

  • TP301
[1] LISMONT J,RAM S,VANTHIENEN J,et al.Predicting interpurch-ase time in a retail environment using customer-product networks:An empirical study and evaluation[J].Expert Systems with Applications,2018,104:22-32.
[2] KIM J,HASTAK M.Social network analysis:Characteristics of online social networks after a disaster[J].International Journal of Information Management,2018,38(1):86-96.
[3] YANG J,LI Y,LIU Q,et al.Brief introduction of medical data-base and data mining technology in big data era[J].Journal of Evidence-Based Medicine,2020,13(1):57-69.
[4] ZHOU F,YIN M M,JIAO C N,et al.Bipartite graph-based colla-borative matrix factorization method for predicting miRNA-dis-ease associations[J].BMC Bioinformatics,2021,22(1):1-16.
[5] XIA W,GAO Q,WANG Q,et al.Tensorized bipartite graph learning for multi-view clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2022,45(4):5187-5202.
[6] WANG K,LIN X,QIN L,et al.Accelerated butterfly counting with vertex priority on bipartite graphs[J].The VLDB Journal,2023,32(2):257-281.
[7] CHEN C,ZHU Q,WU Y,et al.Efficient critical relationshipsidentification in bipartite networks[J].World Wide Web,2022,25(2):741-761.
[8] LIU B,YUAN L,LIN X,et al.Efficient(α,β)-core computation in bipartite graphs[J].The VLDB Journal,2020,29(5):1075-1099.
[9] BATAGELJ V,ZAVERSNIK M.An o(m) algorithm for coresdecomposition of networks[J].arXiv preprint cs/0310049,2003.
[10] KONG Y X,SHI G Y,WU R J,et al.k-core:Theories and ap-plications[J].Physics Reports,2019,832:1-32.
[11] WANG K,ZHANG W,LIN X,et al.Efficient and effective com-munity search on large-scale bipartite graphs[C]//2021 IEEE 37th International Conference on Data Engineering(ICDE).IEEE,2021:85-96.
[12] LIU B,YUAN L,LIN X,et al.Efficient(α,β)-core computation:An index-based approach[C]//The World Wide Web Conference.2019:1130-1141.
[13] MALLIAROS F D,GIATSIDIS C,PAPADOPOULOS A N,et al.The core decomposition of networks:Theory,algorithms and applications[J].The VLDB Journal,2020,29:61-92.
[14] CHAN T H H,SOZIO M,SUN B.Distributed approximate k-core decomposition and min-max edge orientation:Breaking the diameter barrier[J].Journal of Parallel and Distributed Compu-ting,2021,147:87-99.
[15] LIU J,XU C,YIN C,et al.K-core based temporal graph convo-lutional network for dynamic graphs[J].IEEE Transactions on Knowledge and Data Engineering,2020,34(8):3841-3853.
[16] DING D,LI H,HUANG Z,et al.Efficient fault-tolerant group recommendation using alpha-beta-core[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Ma-nagement.2017:2047-2050.
[17] ZHANG Y,PHILLIPS C A,ROGERS G L,et al.On finding bicliques in bipartite graphs:a novel algorithm and its application to the integration of diverse biological data types[J].BMC Bioinformatics,2014,15:1-18.
[18] ALLAHBAKHSH M,IGNJATOVIC A,BENATALLAH B,et al.Collusion detection in online rating systems[C]//Web Technologies and Applications:15th Asia-Pacific Web Confe-rence,APWeb 2013,Sydney Proceedings 15.Springer Berlin Heidelberg,2013:196-207.
[19] BEUTEL A,XU W,GURUSWAMI V,et al.Copycatch:stopping group attacks by spotting lockstep behavior in social networks[C]//Proceedings of the 22nd International Conference on World Wide Web.2013:119-130.
[20] BONCHI F,KHAN A,SEVERINI L.Distance-generalized core decomposition[C]//Proceedings of the 2019 International Conference on Management of Data.2019:1006-1023.
[21] TATTI N.Fast computation of distance-generalized cores using sampling[J].Knowledge and Information Systems,2023,65(6):2429-2453.
[22] CORMEN T H,LEISERSON C E,RIVEST R L,et al.Introduction to algorithms[M].MIT Press,2022.
[1] HU Shuai-peng, ZHANG Qing-hua and YAO Long-yang. Effective Algorithm for Computing Attribute Core Based on Binary Representation [J]. Computer Science, 2016, 43(12): 79-83.
[2] LOU Chang,LIU Zun-ren and GUO Gong-zhen. Quick Attribute Reduct Algorithm on Neighborhood Rough Set Based on Block Set [J]. Computer Science, 2014, 41(Z11): 337-339.
[3] ZHANG Chun-ying and ZHANG Xue. Uncertain Attribute Graph Sub-graph Isomorphism and its Determination Algorithm [J]. Computer Science, 2013, 40(6): 242-246.
[4] LIU Yi,XU Yang,QIN Ya. Interval-valued (α,β)-fuzzy Lattice Implication Subalgebras [J]. Computer Science, 2011, 38(4): 263-266.
[5] LIANG Jun-qi,ZHANG Wen-jun. Relations between for Variable Precision Covering Approximation Operators and Covering Approximation Operators [J]. Computer Science, 2011, 38(3): 222-223.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.