A Discrete Black Hole Optimization Algorithm for Efficient Community Detection in Social Networks

Introduction

In last years, the use of online social networks has increased significantly due to the increasing use of Internet in general and the large availability of various kinds of connected devices such as: desktop computers, laptops and smartphones. Every day millions of people connect to social networking websites to communicate with each other and to share information, which made these websites very popular among others, Facebook and Twitter are the most famous ones. Facebook which was created in 2008 has now more than one billion active users from around the world, this huge number of users makes it the most popular social networking website in the world. Twitter known as the first microblogging website created earlier in 2006 has now more than 200 million active user. The huge amount of data and information shared between people on these websites has made social networks analysis a very important research field.

Social Networks are generally represented by graphs where nodes represent individuals and edges represent the relation between them, for example, in Facebook individuals are people and the relation between them is friendship. A social network is usually found to be grouped into a set of interconnected groups which means that individuals who are very similar between them have strong possibility to be in a same group, these groups are generally known as communities, one can classify communities into two types: Explicit and Implicit ones (Kadushin, 2012). In an explicit community members know that they belong to it and nonmembers know who its members are, Facebook groups are famous example of this type of communities where members can post messages and images, comment on other’s posts and see activities of other people. In the contrary, an implicit community is a community where individuals interact with each other in a form of unknown connections which means that members of such communities do not know that there is a community and that they are members of it, for example people who use same hashtags in their tweets or follow the same celebrities in Twitter form implicit communities. In social networks, researchers are typically interested in finding implicit communities since explicit ones are already known and identified; this task is known as community detection or community discovery.

Community detection is defined as the process of identifying interconnected groups also known as clusters or partitions in a network, it assigns each individual in the network to his/her suitable group. Community detection algorithms are often provided with a graph where nodes represent individuals and edges represent relations between individual, Formally, the task of community detection is to find a set of communities in such that . Community detection algorithms are not specific only to detect communities inside social networks, they have many applications in different domains such us: Biology (Girvan & Newman, 2002), Social (Lozano et al., 2007) and Communications (Faloutsos et al., 1999). In fact, they can be applied to any complex problem that takes the form of a complex network; social networks are a specific type of complex networks. However, these algorithms are extensively used on social networks because of the important applications that can be done, for instance, community detection algorithms are widely used by marketing agencies to find potential clients among millions of people or to detect group of people who have the same food taste to recommend for them a special food product or may be a specific restaurant.