Community Structure Detection Using Firefly Algorithm

Community Structure Detection Using Firefly Algorithm

Ameera Saleh Jaradat (Computer Science Department, Yarmouk University, Irbid, Jordan) and Safa'a Bani Hamad (Yarmouk University, Irbid, Jordan)
Copyright: © 2018 |Pages: 19
DOI: 10.4018/IJAMC.2018100103

Abstract

This article describes how parallel to the continuous growth of the Internet, which allows people to share and collaborate more, social networks have become more attractive as a research topic in many different disciplines. Community structures are established upon interactions between people. Detection of these communities has become a popular topic in computer science. How to detect the communities is of great importance for understanding the organization and function of networks. Community detection is considered a variant of the graph partitioning problem which is NP-hard. In this article, the Firefly algorithm is used as an optimization algorithm to solve the community detection problem by maximizing the modularity measure. Firefly algorithm is a new Nature-inspired heuristic algorithm that proved its good performance in a variety of applications. Experimental results obtained from tests on real-life networks demonstrate that the authors' algorithm successfully detects the community structure.
Article Preview
Top

1. 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)

IJAMC.2018100103.f01

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:

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing