Efficient distance-generalized (α, β)-core decomposition on bipartite graphs
Authors: 
Zhengyu Hua, Yihao Zhang, Long YuanAuthors Info & Claims
Pages 162 - 163
Abstract
(α, β)-core decomposition is a fundamental problem in graph analysis, and has been widely adopted for anomaly detection and online 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 are considered, the new model can identify more fine-grained structure information, which also makes the corresponding (α, β, h)-core decomposition challenging. To address this problem, an efficient algorithm based on computation-sharing strategy is proposed and the time complexity is analyzed accordingly. Experimental results on eight real graphs demonstrate the effectiveness of the proposed model and efficiency of the proposed algorithms.
References
[1]
Vladimir Batagelj and Matjaž Zaveršnik. 2011. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification 5, 2 (2011), 129–145.
[2]
Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos. 2013. Copycatch: stopping group attacks by spotting lockstep behavior in social networks. In Proceedings of the 22nd international conference on World Wide Web. 119–130.
[3]
Monika Cerinšek and Vladimir Batagelj. 2015. Generalized two-mode cores. Social Networks 42 (2015), 80–87.
[4]
Zi Chen, Long Yuan, Li Han, and Zhengping Qian. 2023. Higher-Order Truss Decomposition in Graphs. IEEE Trans. Knowl. Data Eng. 35, 4 (2023), 3966–3978. https://doi.org/10.1109/TKDE.2021.3137955
[5]
Danhao Ding, Hui Li, Zhipeng Huang, and Nikos Mamoulis. 2017. Efficient fault-tolerant group recommendation using alpha-beta-core. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 2047–2050.
[6]
Mehdi Kaytoue, Sergei O Kuznetsov, Amedeo Napoli, and Sébastien Duplessis. 2011. Mining gene expression data with pattern structures in formal concept analysis. Information Sciences 181, 10 (2011), 1989–2001.
[7]
Michael Ley. 2002. The DBLP computer science bibliography: Evolution, research issues, perspectives. In String Processing and Information Retrieval: 9th International Symposium, SPIRE 2002 Lisbon, Portugal, September 11–13, 2002 Proceedings 9. Springer, 1–10.
[8]
Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2019. Efficient (α, β)-core computation: An index-based approach. In The World Wide Web Conference. 1130–1141.
[9]
Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2020. Efficient (α, β)-core computation in bipartite graphs. VLDB J. 29, 5 (2020), 1075–1099. https://doi.org/10.1007/s00778-020-00606-9
[10]
Jun Wang, Arjen P De Vries, and Marcel JT Reinders. 2006. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. 501–508.
Index Terms
- Efficient distance-generalized (α, β)-core decomposition on bipartite graphs
Recommendations
r-Bounded k-complete bipartite bihypergraphs and generalized split graphs
Let P and Q be hereditary classes of graphs. Suppose that the stability number α(H) is bounded above for all H ∈ P, and the clique number ω(H) is bounded above for all H ∈ Q. An ordered partition A∪B=V(G) is called a Ramseian (P,Q)-partition if G(A)∈ P ...
Bipartite almost distance-hereditary graphs
The notion of distance-heredity in graphs has been extended to construct the class of almost distance-hereditary graphs (an increase of the distance by one unit is allowed by induced subgraphs). These graphs have been characterized in terms of forbidden ...
Dominating induced matching in some subclasses of bipartite graphs
AbstractA subset M ⊆ E of edges of a graph G = ( V , E ) is called a matching if no two edges of M share a common vertex. An edge e ∈ E is said to dominate itself and all other edges adjacent to it. A matching M in a graph G = ( V , E ) is ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
173 pages
ISBN:9798400702334
DOI:10.1145/3603165
Copyright © 2023 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 September 2023
Check for updates
Author Tags
Qualifiers
- Poster
- Research
- Refereed limited
Conference
ACM TURC '23
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 36Total Downloads
- Downloads (Last 12 months)32
- Downloads (Last 6 weeks)1
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format