A hybrid approach for enhanced link prediction in social networks based on community detection

Community detection and link prediction are interdependent to a high degree. Knowing the community structure beforehand improves the identification of missing links, whereas clustering on networks with newly introduced missing links improves community detection. In this work, we examine the effectiveness of employing community structure information to predict links in static networks by combining local, quasi-local, and global similarity features to compensate for the weaknesses of each approach. Moreover, we formally defined two classes of links, called relevant links, based on the network's community structure. These links are important because they connect communities or distant nodes within communities. To solve these issues, we developed two hybrid link prediction algorithms based on network communities. To evaluate the effectiveness of the proposed hybrid algorithms, we conducted a comprehensive computational campaign using both real-world and synthetic data-sets. Experiments show that adding information on communities and relevant links enhances the accuracy of link prediction.