Detecting Communities in Heterogeneous Multi-Relational Networks:A
  Message Passing based Approach
  Community is a common characteristic of networks including social networks,
biological networks, computer and information networks, to name a few.
Community detection is a basic step for exploring and analysing these network
data. Typically, homogenous network is a type of networks which consists of
only one type of objects with one type of links connecting them. There has been
a large body of developments in models and algorithms to detect communities
over it. However, real-world networks naturally exhibit heterogeneous qualities
appearing as multiple types of objects with multi-relational links connecting
them. Those heterogeneous information could facilitate the community detection
for its constituent homogeneous networks, but has not been fully explored. In
this paper, we exploit heterogeneous multi-relational networks (HMRNet) and
propose an efficient message passing based algorithm to simultaneously detect
communities for all homogeneous networks. Specifically, an HMRNet is
reorganized into a hierarchical structure with homogeneous networks as its
layers and heterogeneous links connecting them. To detect communities in such
an HMRNet, the problem is formulated as a maximum a posterior (MAP) over a
factor graph. Finally a message passing based algorithm is derived to find a
best solution of the MAP problem. Evaluation on both synthetic and real-world
networks confirms the effectiveness of the proposed method.
