Algorithms for Densest Subgraphs of Vertex-Weighted Graphs

Zhongling Liu, Wenbin Chen (), Fufang Li, Ke Qi and Jianxiong Wang
Additional contact information
Zhongling Liu: School of Engineering, Guangzhou College of Technology and Business, Foshan 510800, China
Wenbin Chen: School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510006, China
Fufang Li: School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510006, China
Ke Qi: School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510006, China
Jianxiong Wang: School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510006, China

Mathematics, 2024, vol. 12, issue 14, 1-9

Abstract: Finding the densest subgraph has tremendous potential in computer vision and social network research, among other domains. In computer vision, it can demonstrate essential structures, and in social network research, it aids in identifying closely associated communities. The densest subgraph problem is finding a subgraph with maximum mean density. However, most densest subgraph-finding algorithms are based on edge-weighted graphs, where edge weights can only represent a single value dimension, whereas practical applications involve multiple dimensions. To resolve the challenge, we propose two algorithms for resolving the densest subgraph problem in a vertex-weighted graph. First, we present an exact algorithm that builds upon Goldberg’s original algorithm. Through theoretical exploration and analysis, we rigorously verify our proposed algorithm’s correctness and confirm that it can efficiently run in polynomial time O(n(n + m)log 2 n) is its temporal complexity. Our approach can be applied to identify closely related subgroups demonstrating the maximum average density in real-life situations. Additionally, we consistently offer an approximation algorithm that guarantees an accurate approximation ratio of 2. In conclusion, our contributions enrich theoretical foundations for addressing the densest subgraph problem.

Keywords: graph mining; densest subgraph; vertex-weighted graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/14/2206/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/14/2206/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:14:p:2206-:d:1434931

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().