A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks

Area of Science:

• Graph theory
• Network analysis
• Data mining

Background:

• Single networks have limitations in modeling complex scenarios.
• Dual Networks (DN), comprising two related graphs with identical vertices but different edges, offer a more comprehensive approach.
• Analyzing common subgraphs within DNs can reveal significant insights.

Purpose of the Study:

• To introduce and formalize the Dual Network approach for complex system analysis.
• To address the computational complexity of finding Top-k Densest Connected subgraphs within DNs.
• To demonstrate the utility of DNs through experimental validation.

Main Methods:

• Formalization of the Dual Network concept.
• Development of a heuristic algorithm to efficiently detect Top-k Densest Connected subgraphs.
• Experimental evaluation on both synthetic and real-world network datasets.

Main Results:

• The proposed heuristic effectively identifies dense connected subgraphs within Dual Networks.
• Experiments validate the approach's capability in revealing sets of highly related nodes.
• The method demonstrates practical applicability for complex network analysis.

Conclusions:

• Dual Networks provide a powerful framework for analyzing intricate relationships in data.
• The heuristic approach offers a computationally feasible solution for a complex graph problem.
• This research advances network analysis techniques for complex systems.