  Finding meaningful communities - subnetworks of interest within a large scale
network - is a problem with a variety of applications. Most existing work
towards community detection focuses on a single network. However, many
real-life applications naturally yield what we refer to as Triple Networks.
Triple Networks are comprised of two networks, and the network of bipartite
connections between their nodes. In this paper, we formulate and investigate
the problem of finding Connected-Dense-Connected subgraph (CDC), a subnetwork
which has the largest density in the bipartite network and whose sets of end
points within each network induce connected subnetworks. These patterns
represent communities based on the bipartite association between the networks.
To our knowledge, such patterns cannot be detected by existing algorithms for a
single network or heterogeneous networks. We show that finding CDC subgraphs is
NP-hard and develop novel heuristics to obtain feasible solutions, the fastest
of which is O(nlogn+m) with n nodes and m edges. We also study different
variations of the CDC subgraphs. We perform experiments on a variety of real
and synthetic Triple Networks to evaluate the effectiveness and efficiency of
the developed methods. Employing these heuristics, we demonstrate how to
identify communities of similar opinions and research interests, and factors
influencing communities.
