A Novel Graphlet-Based Community Detection Algorithm.

Area of Science:

• Network science
• Computational biology
• Data mining

Background:

• Community detection is a key problem in network analysis with diverse applications.
• Existing algorithms face challenges due to the NP-complete nature of the problem and lack of a gold standard definition.
• Defining communities based on uniform, high edge density offers a robust approach.

Purpose of the Study:

• To introduce a novel community detection algorithm based on graphlet sampling.
• To demonstrate the algorithm's superior performance in finding dense and large communities.
• To validate the algorithm's effectiveness in biological networks, including comparison with DREAM challenge winners.

Main Methods:

• The algorithm identifies communities by sampling graphlets (small induced subgraphs) with edge density above a specified threshold (ε).
• These graphlets are conglomerated and merged to form communities with uniformly high edge density.
• The approach is validated against existing algorithms on various network types and specifically on biological networks from the 2016 DREAM challenge.

Main Results:

• The novel algorithm consistently outperforms existing methods in detecting overlapping communities, yielding larger and denser communities.
• Performance was evaluated across biological and non-biological networks, showing near-universal superiority.
• In the 2016 DREAM challenge, the algorithm identified substantially denser communities compared to the winning entries.

Conclusions:

• The proposed graphlet-based community detection algorithm offers a significant advancement over existing methods.
• Its ability to find uniformly dense and large communities makes it highly effective for network analysis, particularly in biological contexts.
• The algorithm's strong performance validates the proposed definition of a community based on edge density.