Article Preview
Top1. Introduction
In the last decade, complex networks analysis and mining has attracted the attention of many researchers from different domains since a lot of real world problems can be handled as complex networks including problems in: Biology, Social, and Communication. Generally, a complex network is represented by a graph where nodes represent individuals and edges represent the relation between them, for example, individuals could be users of a social networking website, computers or web pages and relations could be respectively friendship, internet connection and URL links. Complex networks are found to group into strongly connected groups in general, these groups have a high density of within-group edges and a lower density of between-group edges – nodes have more connections with in-group nodes than out-group nodes. Detecting these groups also known as clusters, partitions or communities is called community detection which is a hot topic in the field of networks analysis.
Community detection is the process of detecting groups of similar individuals inside a network, which means that individuals who share a number of same characteristics between them are grouped in groups called communities. 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 is considered as an NP-hard problem due to the fact that neither the size nor the number of communities is known. However, even with these difficulties several algorithms and methods have been proposed to solve this problem. One can classify these methods into different types (Fortunato, 2010); traditional methods can be classified into two groups: Graph Partitioning and Hierarchical Clustering. Graph Partitioning methods cluster a network into a predetermined number of communities, usually with equal size, these methods require the number and the size of communities before partitioning, the Kernighan-Lin algorithm proposed in (Suaris & Kedem, 1988) is one of the earliest methods for graph partitioning. Hierarchical Clustering methods cluster a network into groups of nodes based on their similarity which means that similar nodes are grouped into communities according to a similarity measure. Cosine similarity, Hamming distance and Jaccard (Singhal, 2001) index are frequently used measures. These methods are classified into two categories:
- 1.
Agglomerative Algorithms: Initially each node represents a partition of its own, then partitions are successively merged until the desired network partition structure is obtained.
- 2.
Divisive Algorithms: All nodes initially belong to one partition, and then the partition is divided into sub-partitions, which are successively divided into their own sub-partitions. This process continues until the desired network partition structure is obtained.
Hierarchical methods have the advantage of not requiring a predefined number and size of partitions. However, they do not provide a way to choose the better partition that represents the community structure of the network from those obtained by the procedure, a detailed classification of community detection algorithms can be found in (Fortunato, 2010). Other algorithms and methods will be discussed later in the next section.