Integer programming models for community detection in relational networks have diverse applications in different fields. From making our lives easier by improving search engine optimization to saving our lives by aiding in threat detection and disaster management, researches in this niche have added value to human experience and knowledge. Besides the community structure, the influential nodes or members in a complex network are highly effective at diffusing information quickly to others in the community. Prior research dealing with the use of optimization models for clustering networks has independently focused on detecting communities. In this research, we propose a new integer linear programming model to detect community structure in real-life networks and also identify the most influential node within each community. We validate the proposed model by testing it on a well-established community network. Further, the performance of the proposed model are evaluated by comparing it with the existing best performing optimization model as well as three heuristic approaches for community detection. The experimental results indicate that in most cases the proposed integer programming model performs better than the existing optimization model with respect to modularity, Silhouette coefficient and computational time. Besides, our model yields superior Silhouette and competitive modularity values compared to the heuristic approaches in many cases.

Introduction

A large number of complex systems can be expressed through networks, which is a group of nodes associated through edges or links (Raghavan et al., 2007). Social networks such as Facebook and Twitter are such examples, where the users are represented by the nodes and the ties/friendship between them is indicated by edges. Similarly, in supply chain logistics, nodes represent the supplier and customer locations, while edges denote the paths connecting the nodes. Due to its theoretical importance and practical applications, research on social, technological, physical and biological networks has gained importance in different branches of sciences. Representing the complex systems through relational networks provides an insight into the intricacy and the dynamic behavior of such systems (Pan et al., 2014). A network is said to exhibit a community structure if its nodes can be grouped into different clusters such that the nodes within the clusters are densely connected compared to the nodes outside the cluster (Radicchi et al., 2004). Finding communities in relational networks takes us one step further to better understanding complex systems, which in turn results in numerous benefits and applications (Girvan and Newman, 2002). Communities are formed by clustering the nodes in a relational network, where the nodes (or objects) are placed into groups such that the objects in the same group have maximum similarities, while the ones in different groups have the least in common.