Article Preview
Top1. Introduction
Due to the ubiquity of the internet the use of internet services becomes very popular such as social networks and internet based marketing. Facebook and twitter represent a very popular examples of social networks and E-commerce represents an example of internet based marketing. Clustering process for these networks depends mainly on the members’ interests. For example in e-commerce, clustering the customers helps in the placement of the products in a good way. Clustering is the task of grouping a set of objects according to their similarities in which each group has the objects that are more similar to each other than those in other groups (Mandala, Kumara, Rao, & Albert, 2013). Social network is a web-based service in which each member is able to create his own profile, create a list of friends, and communicate with all users on the network. The members of the social network share new information and exchange experiences about their interest to find jobs, and for the use of business-to-business marketing.
The problem of detecting community structure in the networks is also known as the graph partitioning problem that divides a graph into several disjoint sub- graphs, called communities (Singh, 2009). These communities are groups of nodes, with a high density of links between nodes of the same group and low density of links between nodes of different groups (Lancichinetti, Kivel, Saramki, & Fortunato, 2010).
A social network can be represented as a graph in which the vertices represent the members, and the edges are corresponding to their interactions (Yin, Li, & Niu, 2014). Given graph G = (V, E), where V is the set of vertex (nodes) and E the set of edges that determines the connectivity between the nodes. Partitioning this graph consists of dividing the graph G into N disjoint partitions by cutting the edges between nodes. Uniform graph partition is one type of graph partitioning (Laszewski, 1993) that consists of dividing a graph into a number of components of the same size and with few relations between them. Graph partitioning is a problem of dividing a set of objects N into a number of partitions P with the goal to minimize the connectivity between the partitions and maximize the connectivity between the nodes in the same partition.
Many problems may be represented as a graph where the partition is a must for some reasons, these problems include scientific computing, load balancing in parallel computing, partitioning various stages of a VLSI design circuit, compiler design, finite element computation and physics, sparse Gaussian elimination, data clustering network partitioning, and task scheduling in multi-processor systems (Andreev & Racke, 2004). Now, the uniform graph partition problem becomes very significant because of its application for clustering and detection communities in social, pathological and biological networks (Patkar & Narayanan, 2003).
Social network clustering is considered as an NP-hard problem (Farshbaf & Feizi-Derakhshi, 2009; Mandala, Kumara, Rao, & Albert, 2013) because it is difficult to find the clusters (partitions) in a reasonable time; therefore, the solutions are based on heuristics. The algorithms that have been used to solve graph clustering problem are evaluated by using the modularity that determine its effectiveness. The modularity (Newman, 2006a; Newman, 2004), the most powerful measurement, is used in the optimization methods in order to detect the community structure in networks. Community detection problem can be considered as modularity maximization. The problem of maximizing modularity is a strongly NP- Complete (Brandes, Delling, Gaertler, Goerke, Hoefer, Nikoloski, & Wagner, 2006). Modularity is defined in (Newman, 2006a; Clauset, Newman & Moore 2004; Newman, 2004) as a function that measures the goodness of a division of any network into sub networks. The value of this function lies in the range [−0.5, 1]. The higher modularity value indicates the effectiveness of partitioning (Newman, 2006a).