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

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.