Extracting Dense and Connected Communities in Dual Networks: An Alignment Based Algorithm

Abstract

Networks-based models have been used to represent and analyse datasets in many fields such as computational biology, medical informatics and social networks. Nevertheless, it has been recently shown that, in their standard form, they are unable to capture some aspects of the investigated scenarios. Thus, more complex and enriched models, such as heterogeneous networks or dual networks, have been proposed. We focus on the latter model, which consists of a pair of networks having the same nodes but different edges. In dual networks, one network, called physical, has unweighted edges representing binary associations among nodes. The other is an edge-weighted one where weights represent the strength of the associations among nodes. Dual networks capture in a single model some aspects that cannot be described by using a standard model. Dual networks can be used, for instance, to capture a co-authorships network, where physical network represents co-authors. In contrast, the conceptual network is used to model topics sharing among a couple of authors by means of edge connections. This allows capturing similar interests among authors even though they are not co-authors. We propose an innovative algorithm to find the Densest Connected Subgraph (DCS) in dual networks. DCS is the largest density subgraph in the conceptual network, which is also connected in the physical network. A DCS represents a set of highly similar nodes. Moreover, since DCS is a computationally hard problem, we propose novel heuristics to solve it. We tested the proposed algorithm on social, biological, and co-authorship networks. Results demonstrate that our approach is efficient and is able to extract meaningful information from dual networks.

Keywords

• DCS
• dual networks
• graph alignment
• social networks