Identifying Maximal Cliques in Large Scale Network

Abstract

Social network analysis is one of the most emerging research topics in the field of computer science. Most of the application areas in social network are computationally hard in nature, as the complexity and size of the network are increasing at an exponential rate. Finding maximal cliques in large scale network is one of such NP-Hard problems. Clique is defined as the complete subgraph where every node within the subgraph is connected to every other node. Probably, it is the most densely connected subgraph in the network. It may correspond to group of people who know each other personally in a social network. Maximal clique
is the complete sub-graph from where if we include an additional node, the completeness property is violated. Maximal clique with maximum number of node is known as maximum clique. Maximum independent set and minimum vertex covering problem are the two variant of maximum clique problem. Identifying maximal cliques in social network may help in understanding the communities evolve in the network. In this work three different types of proposed algorithm have been presented for finding the all maximal cliques in the social network.First one has to eliminate all demerits of Bron-Kerbosch algorithm in the terms of all maximal clique and execution time.Second one is based on Genetic Algorithm which is used to finding all maximal cliques in social network in minimum time.Third one is based on Ant colony optimisation to finding maximal clique.