Search

Efficient enumeration of all maximal cliques in a given graph has many applications in the filed of Graph Theory, Social Network Analysis, Bioinformatics and etc. Recent researches indicate that many networks in our world are complex networks involving massive data. Being as the complete sub-graph, a maximal clique can represent a group of friends who all hang around together. It can also be used to find common sub-topologies in a set of protein structures. However, the large scale of real networks and the exponentially increasing computation time of the clique enumeration problem make most of the existing algorithms unsuitable in the real-world scenarios. Therefore, we present a parallel algorithm Peamc (Parallel Enumeration of All Maximal Cliques) which exploits several new and effective techniques to enumerate all maximal cliques in large-scale complex networks. Experimental results on true-life networks with up to 20 million vertices and 50 million edges show that Peamc can find all the maximal cliques with high efficiency and scalability. [ABSTRACT FROM AUTHOR]

Finding and enumerating subgraphs of different structures in a graph or a network is one of the fundamental problems in combinatorics. One of the earliest subgraph models is clique. However, the clique approach has been criticized for its overly restrictive nature. k-plex is one of the models which are introduced by weakening the requirement of clique. The problem to enumerate all the maximal k-plexes is NP complete. We consider this problem and propose an algorithm Pemp (Parallel Enumeration of all Maximal k-Plexes) for enumerating all the maximal k-plexes. We also propose a strategy to accelerate the pruning. A diameter pruning strategy is proposed. This strategy reduces the number of small maximal k-plexes and improves the performance greatly. We also state the parallel edition of our algorithm to analysis large networks and a load balancing strategy is given. In addition, we evaluate the performance of Pemp on random graphs. [ABSTRACT FROM AUTHOR]