  Discovery of communities in complex networks is a topic of considerable
recent interest within the complex systems community. Due to the dynamic and
rapidly evolving nature of large-scale networks, like online social networks,
the notion of stronger local and global interactions among the nodes in
communities has become harder to capture. In this paper, we present a novel
graphical inference method - GI-OHMS (Graphical Inference in Observed-Hidden
variable Merged Seeded network) to solve the problem of overlapping community
detection. The novelty of our approach is in transforming the complex and dense
network of interest into an observed-hidden merged seeded(OHMS) network, which
preserves the important community properties of the network. We further utilize
a graphical inference method (Bayesian Markov Random Field) to extract
communities. The superiority of our approach lies in two main observations: 1)
The extracted OHMS network excludes many weaker connections, thus leading to a
higher accuracy of inference 2) The graphical inference step operates on a
smaller network, thus having much lower execution time. We demonstrate that our
method outperforms the accuracy of other baseline algorithms like OSLOM, DEMON,
and LEMON. To further improve execution time, we have a multi-threaded
implementation and demonstrate significant speed-up compared to
state-of-the-art algorithms.
