A biased edge enhancement method for truss-based community search

Celebrity Gig
The community found by K-truss vs. the community found by BETCS. The latter contains more nodes that are intuitively close to the query node 8. Credit: Yuqi LI, Tao MENG, Zhixiong HE, Haiyan LIU, Keqin LI

Community Search, which targets a cohesive and meaningful community containing the query node, has drawn intense research interest and had extensive applications in various real-world networks recently.

In contrast to lower-order methods from individual nodes and edges, the truss-based method aims to explore the truss structure of complex networks. Nevertheless, the truss-based hypergraph constructed from the original connected graph is usually fragmented into numerous subgraphs and isolated nodes.

To solve the problems, a research team led by Tao Meng published their new research in Frontiers of Computer Science.

The team proposed a biased edge enhancement method to preserve and enhance the higher-order connectivity in hypergraphs with the fragmentation issue. Extensive experiments are performed on various networks to show that our method can effectively address the fragmentation issue and performs better than some state-of-the-art methods.

READ ALSO:  Amazon hikes UK pay, plans to hire 15,000 seasonal workers

In the research, they mainly study the community search problem based on higher-order structures. Community Search, whose target is to search for a cohesive and meaningful community containing the query node, has drawn intense research interest and has had extensive applications in various real-world networks recently.

In contrast to lower-order methods from individual nodes and edges, the truss-based method aims to explore the truss structure of complex networks. Nevertheless, the truss-based hypergraph constructed from the original connected graph is usually fragmented into numerous subgraphs and isolated nodes.

READ ALSO:  Model disgorgement—the key to fixing AI bias and copyright infringement?

To address the fragmentation issue faced by most of the existing truss-based community search methods, they propose a biased edge enhancement method to preserve and enhance the higher-order connectivity in hypergraphs with the fragmentation issue.

Initially, a coarse subgraph containing the desired communities is identified based on the query nodes. Then, measure the proximity of each node in the subgraph to it. Furthermore, these nodes are divided into several levels based on their proximity values, with nodes at lower levels having higher proximity values.

The edges are then enhanced by connecting lower-level nodes to nodes at the level above them. Finally, an edge-enhanced k-truss community search is performed on the subgraph to obtain the desired communities. Extensive experiments on various networks show that the proposed method can effectively solve the fragmentation problem and perform better than some state-of-the-art methods.

READ ALSO:  Putting the squeeze on computer art

More information:
Yuqi Li et al, A biased edge enhancement method for truss-based community search, Frontiers of Computer Science (2024). DOI: 10.1007/s11704-024-2604-8

Provided by
Higher Education Press

Citation:
A biased edge enhancement method for truss-based community search (2024, March 29)
retrieved 30 March 2024
from

This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no
part may be reproduced without the written permission. The content is provided for information purposes only.

Categories

Share This Article
Leave a comment