Article Preview
Top1. Introduction
In recent decades, the continuous growth of the internet allowed people to share and cooperate more (Emrouznejad, 2016). Complex networks illustrate a variety of systems in nature that are formed by a large number of highly interconnected dynamical entities. The Internet, social networks, biological networks, business networks, etc., are some examples of complex networks (Mitchell, 2006). Complex networks have become more attractive as a research topic in many different disciplines and received enormous amounts of attention from physicists, computer scientists, sociologists, and mathematicians. Complex network theory has been applied successfully to topics of many kinds, such as the Internet, biology, and economics (Clauset et al., 2004).
From the computer science point of view, the complex network is a representation of a complex system in terms of nodes and edges, where a node is an individual member in the system and an edge is a link between nodes if there is an interaction between these members. Based on this, communities (also called clusters) in a network can be defined as a group of nodes (i.e. a sub-graph) having a relatively larger number of edges within them, and a smaller number of edges between groups (Girvan and Newman, 2001). A network with the property of having groups of nodes with much denser intra-group connections than inter-group connections is said to have a community structure (Newman and Girvan, 2004; Lancichinetti, 2009; Newman, 2013). The community structure definition is simulated by Figure 1.
Community detection tends to discover groups in the complex networks. Finding communities in complex networks like social, biological, and technical networks is of a great significance. The extracted communities are interpreted as organizational components in social networks, functional units in biochemical networks, or scientific disciplines in collaboration networks (Lancichinetti, 2009).
Detecting densely connected sub graphs (communities) can provide valuable insights, as a community can embody a functional group in the system. For example, In the protein interaction network, communities correspond to proteins with similar functionality. Also, in citation networks, communities correspond to similar research topic (Nguyen et al., 2014; Newman, 2016; Lozano et al. 2003). The ability to identify these communities will help us to recognize and utilize these networks more effectively.
Figure 1. A simple graph with three communities, enclosed by the dashed circle, this graph consists of three groups of nodes with dense internal connections and sparser connections between groups (Newman, 2013)
Typically, community detection and graph partitioning problems fall under the category of NP-hard problems. However, the number and the size of communities are not previously identified in the problem of community detection, whereas they are defined for graph partitioning problems.
The major challenges usually encountered in the problem of community detection in complex networks are: