Detecting Community Structures Within Complex Networks Using a Discrete Unconscious Search Algorithm

Introduction

The amount of research dedicated to complex networks has increased over the last decades due to its wide range of applications. For example, by researching complex networks, the research community has investigated various phenomena within economic, social, and technological settings (Chen & Redner, 2010). Within these problem areas, social structures can also be represented as a complex network. Social networks consist of a set of communities, which are sometimes referred to as called clusters or modules. This particular area of study is also receiving more attention from the research community. For example, Internet social networks (Lambiotte & Ausloos, 2005), scientific reference networks (Chen & Redner, 2010), biological networks (Diao, Li, Feng, Yin, & Pan, 2007), neurological networks (Schwarz, Gozzi, & Bifone, 2008), epidemiology networks (Sun & Gao, 2007), transportation networks (Barigozzi, Fagiolo, & Mangioni, 2011), and even political networks (Porter, Mucha, Newman, & Friend, 2007) are some of the areas being investigated by practitioners and researchers.

Detecting the structure of the communities within a network receives a lot of attention from the research community because it plays a vital role in understanding the behavior among the various communities within a network (Gleich & Seshadhri, 2012). To detect the structure of the communities within a complex network, a clustering operation is used (Zhou, Yang, Xie, Yang, & Huang, 2019). As a result, decision-makers can make better, more informed, and more effective decisions depending on the application of the complex network being investigated.

Detecting communities in a social network is an NP-hard problem. Given this complexity, several methods have been proposed in the literature involving this particular problem. For example, spectral methods, divisive methods, agglomerative methods, maximization of the modularity, local methods, method selection, and roles of vertices are methods dedicated to detecting the structure of the communities within complex networks (Costa, Rodrigues, Travieso, & Villas Boas, 2007). The unconscious search (US) algorithm is a method that is designed to tackle the continuous optimization problems (Ardjmand, Park, Weckman, & Amin-Naseri, 2014). However, the unconscious search algorithm can be modified to solve discrete optimization problems. In this paper, the US algorithm is explored as a community detection method. Using the US algorithm as a method for detecting community structures has not been previously explored by researchers. Thus, the focus of the research presented in this paper involves a comprehensive comparative study of how well the US method preforms when comparing its results against other state-of-the-art methods found within recent academic research.

The comprehensive comparative study presented in this paper is primarily based on the concept of modularity, which is a popular measure in community detection literature. This measure is utilized to determine the strength of the division of a network. In other words, to detect the structure of the communities within a social network, a network can be partitioned in a manner that creates a subset of nodes containing a maximum number of internal links while minimizes the number of possible links with nodes outside of a given cluster (Girvan & Newman, 2002).