Efficient Rational Community Detection in Attribute Bipartite Graphs

Chen Yang, Hao Ji, Yanping Wu and Chunlai Chai

Mathematical Problems in Engineering, 2022, vol. 2022, 1-9

Abstract: Bipartite graph is widely used to model the complex relationships among two types of entities. Community detection (CD) is a fundamental tool for graph analysis, which aims to find all or top-k densely connected subgraphs. However, the existing studies about the CD problem usually focus on structure cohesiveness, such as α,β-core, but ignore the attributes within the relationships, which can be modeled as attribute bipartite graphs. Moreover, the returned results usually suffer from rationality issues. To overcome the limitations, in this paper, we introduce a novel metric, named rational score, which takes both preference consistency and community size into consideration to evaluate the community. Based on the proposed rational score and the widely used α,β-core model, we propose and investigate the rational α,β-core detection in attribute bipartite graphs (RCD-ABG), which aims to retrieve the connected α,β-core with the largest rational score. We prove that the problem is NP-hard and the object function is nonmonotonic and non-submodular. To tackle RCD-ABG problem, a basic greedy framework is first proposed. To further improve the quality of returned results, two optimized strategies are further developed. Finally, extensive experiments are conducted on 6 real-world bipartite networks to evaluate the performance of the proposed model and techniques. As shown in experiments, the returned community is significantly better than the result returned by the traditional α,β-core model.

Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/mpe/2022/4430087.pdf (application/pdf)
http://downloads.hindawi.com/journals/mpe/2022/4430087.xml (application/xml)

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:hin:jnlmpe:4430087

DOI: 10.1155/2022/4430087

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().