A degree-based block model and a local expansion optimization algorithm for anti-community detection in networks.

Area of Science:

• Network analysis
• Graph theory
• Data mining

Background:

• Anti-community detection identifies negative relationships in networks.
• Existing methods often neglect node degree and incur high computational costs.
• Block models offer modularity exploration but depend on observed structures.

Purpose of the Study:

• To propose a novel Degree-based Block Model (DBM) for anti-community detection.
• To develop an efficient Local Expansion Optimization Algorithm (LEOA) for identifying anti-communities.
• To introduce a synthetic benchmark (DBM-Net) for evaluating anti-community detection algorithms.

Main Methods:

• Developed a Degree-based Block Model (DBM) incorporating node degree into an objective function Q(C).
• Proposed a Local Expansion Optimization Algorithm (LEOA) with three stages: structural center detection, local expansion, and membership adjustment.
• Created a synthetic benchmark network, DBM-Net, for evaluating algorithm performance.

Main Results:

• DBM effectively considers node degree for anti-community structure.
• LEOA demonstrates efficiency and effectiveness in detecting anti-communities, prioritizing high-degree nodes.
• Experiments on large-scale synthetic and real-world networks validate the proposed methods.

Conclusions:

• The proposed DBM and LEOA offer a significant advancement in anti-community detection.
• LEOA provides an efficient and effective solution for identifying negative relationships in networks.
• DBM-Net serves as a valuable tool for benchmarking future anti-community detection algorithms.