Abstract
A graph is a network that can represent the communication between a variety of data elements. The data can have uncertainty, primarily due to the heterogeneity of data sources. Moreover, it is sometimes difficult to assure the existence of a link between data elements; compelling to consider the data as a probabilistic entity. Extracting densely connected regions from a graph is a key task of the intelligent systems. The enumeration of dense substructures in a graph can help to identify important patterns. This can have many applications in medical image processing, accident analysis, and surveillance, to name a few. One such dense substructure is a clique, where all nodes are directly connected to each other. An α-maximal clique in an uncertain graph is a clique with a minimum probability α, such that it is not a subset of any other clique of the same weight. Extracting all α-maximal cliques is an NP-Complete problem. This work focuses on reducing the time consumed to enumerate all α-maximal cliques in a graph. Another focus of this work is to reduce the CPU (Central Processing Unit) cycles for efficient enumeration of all α-maximal cliques. An algorithm is proposed that computes all weighted maximal cliques in an uncertain graph. The worst-case asymptotic time complexity of the algorithm is O(n2 n ). The proposed algorithm utilizes the h-index concept to form cliques with vertex degree greater than h. The algorithm builds cliques at two levels of enumeration. The first level finds the α-maximal cliques with a descending order in sizes. On each successive α-maximal clique iteration of the first level, the second level tracks and deletes all subsets of the clique. The second level is to ensure the fact that all subsets of an α-maximal clique are cliques. The proposed algorithm is compared with two recent maximal clique enumeration algorithms, namely: MULE (Maximal Uncertain Clique Enumeration) and LMC (Listing all maximal cliques in large sparse real-world graphs). Real-world benchmark uncertain graphs are utilized for the experimental evaluation. The results suggest better performance of the proposed approach in terms of the time consumption.
Introduction
A graph is a tool to model the real-world relational data in a natural fashion. The use of large graphs is common in a variety of domains. For example, it finds its application in social networks [21], information retrieval [4, 30] citation networks [24] and physical simulation/modeling [15, 28]. The extraction of useful information from such massive datasets is reduced to the problem of enumerating in large graphs. Such large graphs are challenging and sometimes difficult to understand when used with the underlying complex structures. Extracting absolute information directly from such large datasets is not trivial. Therefore, one must build a graph of these massive datasets having some associated probabilities. An effective case of such data can be understood from the protein-to-protein interaction networks, where every link between a pair of nodes has an associated probability [28].
Extraction of patterns from such large graphs is an active research domain these days. As a subdomain of data mining, the extraction of dense zones can assist to find the compelling relationships. These dense zones are used to identify the links which are closely related. Therefore, finding the dense areas, like cliques, bicliques, quasi-cliques, and quasi-bicliques is an active field of research [20]. The work in [23] directs attention towards cliques as the most elementary dense substructure that can be examined in a graph. It finds the maximal cliques by applying a top-down approach. The problem is specifically referred to as Enumeration of Maximal Cliques by Top-Down Approach (EMCTD). Numerous graph mining techniques have been utilized for enumeration of maximal cliques to determine the important substructures within graphs. Such maximal clique enumeration is effectively used for the purpose of community discovery and clustering in biological as well as in social networks. Finding cliques also has its utility in genes co-expression under stress [27], integrating various kinds of genome mapped data and some other applications from bioinformatics and data mining [27]. Although the extraction of single clique in a graph is not complicated, the enumeration of all maximal cliques is a complex problem and is known to be NP-complete [11, 17]. However, some classical cases of this problem are solvable. For example, there exist some output polynomial time algorithms for which the theoretical running time is bounded by the total number of nodes in the graph. In some cases, it is bounded by the total number of patterns that are extracted [19]. Therefore, it is reasonable to design an algorithm that works for some specific size or any specific number of cliques that are extracted by identifying that the total number of maximal cliques is not high.
The key motivation of this work is to design, implementation, and evaluation of a technique to enumerate fundamental dense substructure, i.e., maximal cliques, from large uncertain (probabilistic) graphs. Even though the enumeration of cliques has been studied well, most of the previous approaches to address this problem work in limited scenarios. For example, many of these techniques only examined the graphs with rather a small number of edges or vertices, with an objective to list a few thousand cliques at most. For example, a very popular consensus algorithm [9], that is meant for the bicliques enumeration mentions its experiments on 2000 nodes and 140000 maximal bicliques only. Some other research studies like [10] and [8] also evaluate their results for small scale graphs. This work proposes an algorithm to solve the fundamental problems for the large uncertain graphs. There exist many datasets which hold uncertain information. Based on the available information, they contain uncertainty up to some extent, represented as the existential probability. For two vertices A and B, it is desirable to affirm the relationship from A to B. Therefore, for the given parameters, the quantitative measures are computed that collectively include the effect of these parameters. This quantitative measure is computed as a probability p of the relation. This research work is based on the uncertain graph which contains information as uncertain edges. Each edge of the graph consists of uncertainty about its occurrence. Detection of the dense regions in uncertain graphs is a primary assignment in the domain of intelligent systems. It includes the clustering of networks to make it simple and less challenging. Clustering plays a vital role in the community detection in biological and social networks. A completely connected sub-graph is called a clique.
A sample graph and various cliques extracted.
Summary of the past works on clique finding
In a probabilistic graph, a set of nodes U represents an α-maximal clique if the product of probabilities of all edges between its nodes is at least α, and there is no superset U’ of U, for which the product of edge probability is more than/equal to α. Whenever the value of α becomes 1, it represents a deterministic graph. In such cases, a maximal clique is easy to be verified. In the proposed algorithm here, the α-maximal verification on a subset of a graph is carried out in two steps. The first step checks weather the subset of a graph is a clique or otherwise, and the second step validates the α-maximal only for those subsets which are identified as cliques in the first step. To test the subset as a clique or otherwise, this work finds the column count (C count ) for all the non-zero entries of each column in the adjacency matrix of that specific subset. If all the C count entries are one less than the total count of the subset elements T count , i.e., C count = T count –1, then the subset is a clique. Considering the sample graph given in Fig. 1. and its associated adjacency matrix, the subsets {A, B, C} and {A, D, C, D} form cliques. On the other hand, the sets {A, E, F} and {A, C, E, F} are not cliques. Afterwards, to verify a clique as an α-maxima, the lower triangular multiplication T mult iscomputed. If the lower triangular multiplication of a clique is greater than or equal to the provided probability threshold (α), i.e., T mult ≥α then the clique will be an α-maximal. For the example, in Fig. 1, the subsets {A, B, C} and {A, B, C, D} that were proven to be cliques in the first step are α-maximal clique and non α-maximal clique, respectively.
It is important to know the number of α-maximal cliques possible in a probabilistic graph. For a non-probabilistic graph, the question of enumerating all possible maximal cliques is addressed by Guha et al. [16]. They explored the upper and lower bound of maximal cliques of the graph with n nodes. It was concluded that the total maximal cliques can never exceed
The current proposal presents algorithms to enumerate all α-maximal cliques in an uncertain data. An edge belonging to a graph with the probability p < α can never be part of an α-maximal clique. In this work, first of all, the edges having a probability p < α are pruned. By doing this, information about any α-maximal clique is not lost. However, it decreases the search space to find α-maximal cliques. The maximal clique enumeration problem is that of finding the consensus in an uncertain graph G of all those nodes set S ⊆ V such that S is an α-maximal clique in the graph G. Using this definition, this work has following key observations. If there exist two cliques C1 and C2 in a graph G, and C2 ⊂ C1 then P
c
(C2) > P
c
(C1), where P
c
represents the clique probability. Let E be the total number of in a graph G. If there exists an α-clique in G then it is understood that all the edge subsets E
c
⊆ E will have P (E
c
) > α, where E
c
represent edges of some clique C and P(E
c
) accounts for the uncertainty of that edge.
To reduce the running time, one of the recent algorithms for this task, MULE (Maximal Uncertain Clique Enumeration) [1], gives efficient results. However, it introduces redundancy in clique enumeration due to being a bottom up approach. The work presented in this paper introduces three methods for the enumeration of all α-maximal cliques. Apart from the enumeration of α-maximal cliques, it also explores the minimum limit of probability threshold for any particular size of maximal cliques in uncertain graphs. The worst case time complexity of the proposed approach is O(n2 n ). The experimental analysis shows that, for specific graphs with dense network structure, the proposed approach performs better as compared to the previous techniques. In terms of the running time, the efficiency of the proposed approach depends on the type of graph. Table 1 lists the summary of key past methods on finding maximal cliques in a graph.
The rest of this paper is organized as follows. Section 2 contains the closely related work on finding cliques in a graph. Section 3 presents the proposed approach. Section 4 details the experiments conducted and the results obtained. Finally, Section 5 concludes this work.
Related work
This section covers the literature review of a number of different techniques for finding cliques in a graph. The section starts with details about the origin of the enumeration of the maximal cliques before detailing the recent work. Initial work in this domain is done by Bron and Kerbosch that presents an efficient algorithm to extract cliques [3]. Their approach is based on the depth-first search strategy. Their study presents experimental results on ordinary data inputs. Another research with an algorithm proposed for finding cliques is that of Tomita et al. [6]. There exist other maximal clique enumeration algorithms with running time dependent on the output. For one such algorithm, the running time is O(|V||E|u), where u represents the required number of maximal cliques [19].
There has been some work on maximal clique enumeration using parallel methods [14, 25]. These parallel algorithms stem from the initial work by Kose et al. [7]. They count the maximal cliques using the breadth first search (BFS) strategy. Their proposal is useful for enumeration in expanding order; however, a huge storage space is required for their approach. Another research work in explained an algorithm that is parallel in nature, but depends on the output size [14]. According to authors in [13], this algorithm has the drawback of workload balancing and uses the limited size of the graph with maximum 150,000 maximal cliques and few million edges.
Schmidt et al. analyze the problem of load balancing for parallel maximal clique enumeration [13]. The authors present a novel parallel algorithm that adopts the “work stealing” for the purpose of distributing the load. The limitation of this work is the utility of the MapReduce model. In their model, all processors are synchronized and each processor appeals to work in parallel until it could not find any parallel process to work with. At this stage, they get idle. In this way, at times, all of the processors adopt the idle state. Due to this synchronization of processors at each stage of reducing map model, the complexity of the algorithm is quite high.
In order to address the issue of computational complexity of the clique-finding problem, Wu et al. present a novel algorithm for the enumeration of maximal cliques based on MapReduce model [2]. Their algorithm first divides the graph into multiple independent subgraphs. Afterward, it uses these independent subgraphs to enumerate the maximal cliques. However, their approach has two drawbacks. First, it does not take into account the issue of load balancing. Second, the approach may enumerate some non-maximal cliques as well, due to which it requires an extra step to exclude non-maximal cliques.
Lu et al. [12] present dMaximalCliques, a parallel algorithm which, in turn, is built on the sequential algorithm designed by Tomita et al. [6]. It has two main stages. In the first stage, it calculates a mixture of non-maximal, duplicate and maximal cliques. In the second stage, it discards the non-maximal and duplicates from the output of the first stage to separate the maximal cliques. The first stage can be very expensive because it can rise to an enormous size as compared to the concluding output. The approach in this work is also a sequential one. However, as compared to the algorithm proposed by Tomita et al., it does not require the second stage. This is because, at the time of enumerating each maximal clique, it already indicates the non-maximal cliques and excludes them to be considered for verification as non-maximal.
Another research problem in the domain of dense substructure mining from deterministic graphs is the enumeration of maximal bicliques [22]. Biclique is a special complete bipartite graph having two vertex sets. Every node of the first set is connected to every node of the second set. Uno et al. exemplify the approach for the enumeration of maximal bicliques [22]. Their experimental results show that the delay between two consecutive resulting bicliques is delimited by the largest degree of the graph. To address the same problem of enumeration of bicliques, authors in Zhang et al. propose a new algorithm entitled “branch-and-bound” [26].
There is yet another issue of finding the induced maximal bicliques in a graph. An induced maximal biclique is a biclique with both vertex sets of a bipartite graph being independent. In this case, independence is defined as the absence of an edge between the vertices of an individual set of the bipartite graph. For example, consider < M, N >to be an induced biclique of a graph G, then this would imply that there is no edge between any nodes of set M in graph G; the same goes for the set N. The preliminary work on maximal bicliques was done by Eppstein [5]. A non-induced biclique is basically a biclique for which there can exist some edges between each individual vertex-set. An iterative algorithm for the purpose of enumerating non-induced maximal bicliques is based on the consensus mechanism as proposed by Alexe [9]. By implementing the depth first search (DFS), a new algorithm for enumerating the maximal bicliques is proposed Liu et al. [8] and as well as Li et al. [10]. Similarly, using the basic concept presented by Uno et al. [22], a new an approach is proposed on a connection with mining closed patterns for a dataset from transactions in [10].
Research has also been conducted on parallel methods for the purpose of enumerating maximal bicliques. Nataraj, and Selvan [18] compare the methods of maximal bicliques with the closest pattern presented by Li et al. [10]. The authors utilize a parallel algorithm to enumerate maximal biclique. This approach uses graphs as an adjacency matrix, followed by the conversion of those matrixes into the transaction dataset. The work in [31] focuses on enumerating Δ-cliques. This is an extension of the notion of cliques in temporal graphs. A backtracking algorithm, i.e., Bron–Kerbosch method is used to enumerate all maximal cliques in a temporal graph setting. The concept of Δ-degeneracy is utilized for the theoretic analysis. An approach is presented in [32] to extract maximal cliques by improving the branch-and-bound approach. Three methods are suggested. The first approach employ variant of an approximation algorithm (KLS) to extract cliques. The second method sorts vertices near the root of the search tree. Finally, the third method utilizes a lightened approximate coloring close to the leaves of the search tree. Segundo et al. [33] adopts bit-parallelism to demonstrate that greedy pivot selection based on a constant upper bound of degree first ordering of vertices performs better. The simple greedy pivot selection strategy adopted in [33] allows to pivot without enumeration. This results in consuming less execution time. Conte et al. [34] extend the clique finding task to the directed graphs. A number of useful properties are listed and a tighter bound is suggested for the problem. A few other related approach on pattern extraction from graphs can be seen in [35–39].
While the aforementioned approaches studied the clique finding problem for deterministic graphs, the present study focused on finding reliable subgraphs by extracting the maximal cliques for which the nodes are linked with a certain edge probability. The extracted subgroups may be dense or sparse. This research study explores only those subgraphs which have the cumulative probability of edges greater than a given threshold. Previous work explores the enumeration of dense substructures for an uncertain graph to a limited extent. An initial study on the enumeration of α-maximal cliques in a probabilistic graph is presented Zou et al. [29]. Afterwards, Mukherjee et al. presented a new depth-first search method, namely MULE (Maximal Uncertain cLique Enumeration), for the mining of dense substructures [1]. They primarily spotlight the enumeration of all maximal cliques. On the other hand, Zou et al. explore a particular problem of enumerating only k-maximal cliques [29]. MULE gives effective results for running time with the worst case running time complexity of O(n2 n ). The MULE approach does not address the two most important issues. The first issue is the redundancy in clique enumeration due to the depth-first search while the second issue is the incremental buildup of probabilities that can be very expensive. This research work addresses these two problems to reduce the running time. This issue is fixed by applying the top-down approach, because the top-down approach does not require an incremental update of the probabilities.
Proposed solution
This section presents a detailed explanation of the three approaches proposed in this work for clique finding. The section first explains a direct approach for the maximal clique enumeration using MULE [1]. A brief explanation of MULE is as follows.
Let V be the set of vertices in a graph G. and suppose that T (v) expresses the set of all nodes that are connected to the vertex v ∈ V in G. It can be easily verified that every clique C ⊆ V is also a clique in G v for any node v ∈ C but can never be a maximal clique. The parallel algorithm for the enumeration of maximal cliques operates in two steps. The first step, while operating in parallel, generates all possible subgraphs. After that, the second step explicitly finds the maximal cliques of all subsets that are generated in the first step through sequential maximal clique enumeration algorithm. The technique mentioned above has three deficiencies. One of the obvious drawbacks is that the parallel algorithm cannot get rid of the duplicate cliques in the extracted maximal cliques. Each clique C is enumerated m times, where m is the total number of clique nodes. The approaches presented by Wu et al. [2] and Lu et al. [12] remove this duplication with the use of a post-processing step. However, that post-processing step has the main issue of intervening output size. For the parallel approaches, due to the duplication issue, the size of intervening output can extend to a very large value as compared to the final output. The second deficiency is that of redundancy in the enumeration of maximal cliques. For all the possible subgraphs G V , there is a separate processor required. This separate computation does not share information. Due to this non-communicative behavior, the computation of a clique of size m is repeated m times The third issue is that of load balancing. This issue arises because different sub-problems related to different nodes can differ enormously in size. A node that is a member of many maximal cliques, or is part of a maximal clique with comparatively large size, will be computationally expensive as compared to a node that is part of a smaller maximal clique. Therefore, the distribution of the workload across the different sub-problems is uneven.
Key contributions
Keeping in view the above limitations, this work utilizes a top-down approach for the enumeration of maximal cliques. The top-down approach is executed by initially finding the maximal clique of the larger size; then going down the tree to find the maximal cliques of smaller sizes. There can be many overlapping cliques in a graph of the same size. Let C ⊆ V be a maximal clique of the maximum size s, then all the cliques C' ⊆ V with the size smaller than s will always be cliques. However, they cannot be maximal cliques. The problems discussed above are resolved efficiently as explained below.
Elimination of duplicate maximal cliques: One of the key advantages of the proposed approach is that there is no need for the post-processing step to eliminate the duplicate maximal cliques. As compared to the previous approaches described in Section 2, the proposed approach never results in the duplication of maximal cliques. This is because the cliques that seem to be duplicated are eliminated in the first step; thus no extra step is required for their elimination. The avoidance of duplication is done by generating unique subsets in the first step that differ in the vertices; only these unique subsets are evaluated for further processing.
6. clique_matrix←∅
7. ListM - A←Max_Clique_Enum (Matrix, α, List)
Elimination of redundant work: The previous approaches like Bornet et al. [6] use a bottom-up strategy for the enumeration of maximal cliques. In their approach, they first check for the maximal clique of smallest size and then go on to examin the maximal clique of larger size by adding more vertices. This methodology is required for the bottom-up approaches, because if there is a clique C ⊆ V of size k then there is a possibility that it will not be a maximal clique. Suppose that there exists a maximal clique C' ⊆ V of size k + m for any positive integer m, such that C' ⊇ C. Then, there is no need to check for the subsets, since it cannot be a maximal clique. The same concept is utilized in this research work. At any stage, if a maximal clique is found then there is no need to examine its subsets. This way, redundant effort is eliminated. Improved load balancing: The problem of load balancing is solved by maintaining the specific size of subgraphs at each stage. The proposed approach first finds all subgraphs of the largest size k, where k is the maximum degree of the graph. Once all the subsets of the maximum size are examined, the subgraphs of size k-1 are examined. During each stage, the number of vertices in the sub-graphs, i.e., the size of the graph, does not vary. Therefore, the number of steps required for examining the maximal clique remains constant. As a result, the computational cost of the algorithm depends on the number of vertices, which is a constant, in contrast to the earlier approaches in which it was variable [3, 6]. Hence, the problem of load balancing is resolved efficiently. This research study presents three different approaches for the enumeration of the maximal clique to reduce the running time of the algorithm. These are explained in the following sections. The proposed methodology here is named EMCTDS (Enumeration of Maximal Cliques: A Top Down Strategy). The EMCTDS enumerates all α-maximal cliques in an uncertain data. The EMCTDS methodology internally comprises of following three algorithms.
Excluding-(k+1) method (EMCTDS Approach-1)
To enumerate all maximal cliques, all subsets of a graph having n vertices need to be generated. The generation of all subsets consumes 2
n
steps. Thus, the overall complexity of the algorithm becomes O(2
n
). However, the number of nodes in the largest clique cannot exceed k+1, where k is the largest degree of any vertex available in the graph. Therefore, instead of considering all subsets, the first approach here excludes all those subsets with the number of nodes larger than k+1. This decreases the number of steps to enumerate all cliques by consuming only
Max node stop method (EMCTDS Approach-2)
The second approach first checks whether a subset of size k+1 is a clique. It then checks for the sizes of k, k-1, k-2, and so on. As mentioned in the above approach, k+1 is the size of the largest possible clique where k is the highest degree in a graph. For any subset, if it is confirmed to be a clique then there is no need to check for the subsets of that specific subgroup. This is because the subset of a clique is also a clique.
h-Index method (EMCTDS Approach-3)
This approach is an h-index-based technique. According to this method, if a clique of size k is to be extracted then only those vertices having degree N
d
≥ k are considered. The total number of such nodes must be greater than or equal to k, i.e., Num (N
d
) ≥ k, where, N
d
represents the node of degree d and Num (N
d
) stands for the total number of nodes having degree d. As an example, consider the graph and its associated adjuncency matrx shown in Fig. 2. To find a maximal clique of size four in the graph, only the vertices A, E, F, G and H will be considered. This is done by discarding the vertices B, C, and D. Similarly, to find the maximal clique of size three, only the vertices A, B, E, F, G, and H will be considered, while discarding the vertices C and D. Algorithms 1, 2, and 3 lists the pseudocode of the proposed approaches. A sample graph explaining h-index-based clique finding technique. Summary of the datasets
This section presents a detailed analysis of the proposed technique using numerical simulations. A number of simulations are performed using the proposed solution and two state-of-the-art clique finding methods, namely, MULE (Maximal Uncertain Clique Enumeration) and LMC (Listing all maximal cliques in large sparse real-world graphs). The proposed solution is implemented using MATLAB 7.10.0. The simulations are performed on a system having of 1.86 GHz Intel® CoreTM i3 processor and 2 gigabyte RAM. During these simulations, a heap space of 1.8 GB was maintained.
Datasets
In order to carry out the simulations, using the three competing approaches, seven benchmark datasets were utilized. A summary of these is listed in Table 2. These datasets can be categorized into two main groups. The first group of datasets consists of FruitFly, DBLP, and PPI. The Fruitfly dataset was collected by combining the datasets from the two archives, i.e., BioGRIDrmbox1[1]http://thebiogrid.org/ database and STRINGrmbox2[2]http://string-db.org/ database. The DBLPrmbox3[3]http://dblp.uni-trier.de/ dataset is a probabilistic data used to forecast the future co-authorship between different researchers. This dataset represents the co-authorship information in academic articles. Every node in this graph represents an author. The edges between the nodes represent the probability indicating durability of their co-authorship. The PPI is also a probabilistic database in which every node serves as a protein. The uncertainty of the relationship between the two nodes exhibit the tendency of communication between them. The second set of databases consists of p2p-Gnutella08, p2p-Gnutella04, p2p-Gnutella09, ca-GrQc, and wiki-vote. These mirror the peer-to-peer networks where ca-GrQcand and wiki-vote mirror the collaboration networks and online social networks, respectively. These datasets were obtained from Stanford Large Network Collectionrmbox4[4]https://snap.stanford.edu/data/. The p2p-Gnutella dataset contains information about peer-to-peer file exchanging network. In this graph, the nodes serve as the computer devices whereas the links between them represent the file communication. The p2p-Gnutella08, p2p-Gnutella04, and p2p-Gnutella09 datasets shows the peer-to-peer file exchange that took place on 4th, 8th, and 9th of August, 2002, respectively. The ca-GrQc graph stands for the partnership among the researchers doing research in the field of general relativity and quantum cosmology. Every node stands for a researcher, and any two of them have an edge between them if they have a partnership with each other in their research paper. Lastly, the wiki-vote graph dataset comprises of nodes representing Wikipedia administrator, Wikipedia user or Wikipedia candidate. This graph shows the voting for a newly elected Wikipedia administrator. There exists an edge between two nodes if the Wikipedia user or administrator casts a vote in demand for a candidate.
Execution time consumed by the competing methods.
MULE (Running time vs. probability threshold α)
In order to analyze the performance of the three competing methods in the enumeration of all α-maximal cliques, a set of numerical simulations has been carried out. For these simulations, the value of alpha was set to be 0.8 for all datasets. The results show that the running time for two of the proposed techniques, i.e., max node stop method and h-index method is less than that of the MULE and LMC. The running time for the excluding-(k+1) method is less than that ofLMC; however, it is higher than running time ofMULE. Figure 3 lists these running times over the seven benchmark datasets.
Running time vs. probability threshold (α)
A second set of numerical simulations have been carried out using the three proposed approaches as well as MULE using the seven datasets to compute the running time taken for different values of the probability threshold α. The results for this are shown in Tables 3–6. The results show that when α increases, the running time decreases for all techniques. In the case of h-index method (EMCTDS approach-3), as the value of α increases, the running time decreases sharply as compared to the other two methods. For example, the running time of MULE for amazone03 decreases from 20281 seconds to 19039 seconds for the change of α from 0.001 to 0.007. However, the running time of h-index method (EMCTDS approach-3), for the same change of α and the same dataset, decreases from 17320.97 seconds to 15820.96 seconds. Similarly, in the case of DBLP dataset, the running time for the MULE and h-index method decreases from 29812.12 to 22691.88 and 28981.83 to 19297.83, respectively. The results show that, as compared to the other two approaches, the proposed approach is quicker when the value of α increases.
EMCTDS-Approach-1 (Running time vs. probability threshold α)
EMCTDS-Approach-1 (Running time vs. probability threshold α)
EMCTDS-Approach-2 (Running time vs. probability threshold α)
EMCTDS-Approach-3 (Running time vs. probability threshold α)
MULE (α vs. no. of cliques)
EMCTDS-Approach-1 (α vs. No. of cliques)
A third set of numerical simulations have been carried out using the three proposed techniques and MULE to test the total number of α-maximal cliques found against different values of the probability threshold α. The results of this experiment are shown in Tables 7–10. As the value of α increases, the number of α-maximal cliques decreases. The decrease in the number of α-maximal cliques is due to the fact that as the value of probability threshold increases, a very small number of cliques passes through this threshold. It is also worth noticing that the value of α-maximal cliques does not necessarily decrease as the probability threshold increases. This is due to the reason that sometimes the larger maximal cliques with small threshold value of α may not pass through the high threshold value and may split into multiple smaller ones. Thus, this phenomenon results in the increase of number of rα-maximal cliques.
EMCTDS-Approach-2 (α vs. No. of cliques)
EMCTDS-Approach-2 (α vs. No. of cliques)
EMCTDS-Approach-3 (α vs. No. of cliques)
A fourth set of numerical simulations has been carried out for varying number of vertices in the datasets for the five competing methods to extract α-maximal cliques. For this analysis, amazone0302 dataset is utilized. The results for this are shown in Fig. 4. For the amazone0302 dataset, a total of 10000 random edges were increased in each iteration of the experiment. This shows increase in the running time with an increase in the number of uncertain edges. The increase in the time consumed is significant for the dense graphs. This abnormal trend shows that there can be many more α-maximal cliques than the number of certain cliques for an uncertain data. The results in Fig. 4 demonstrates that the proposed approaches in this work are efficient in quickly enumerating all α-maximal cliques as compared to MULE and LMC. For example, in a case of amazone0302, this the proposed method only requires 2531 seconds to complete, whereas, the other two methods require 4192 seconds for 60000 uncertain edges.
Performance analysis of the competing approaches using no. of vertices vs. running time consumed to extract α-maximal cliques.
Size threshold vs. running time.
Finally, a fifth set of numerical simulations has been carried out using the h-Index method (EMCTDS approach-3) and MULE on different datasets to see the effect of threshold size on the running time. The size N is the minimum size of α-maximal clique that was extracted. The results are shown in the Fig. 5. When the size threshold of the α-maximal clique increases, the running time also increases. The running time for the proposed approach is much less as compared to that of MULE. For instance, the proposed approach takes 8358 second to enumerate all uncertain maximal cliques from the DBLP (with a probability threshold of 0.2). One the other hand, the MULE method takes 9982 seconds when N = 6. Similarly, in the case of CA-GrQc, with α set as 0.0001, the proposed approach takes 5361 seconds, whereas MULE takes 6102 seconds when N = 5. It is also important to note that for the higher threshold values this proposal performs much faster as compared to the lower threshold values. As the threshold increases, the proposed methods get faster. This trend is due to the top-down methodology adopted here. As the threshold increases, the smaller cliques incrementally add up to form the bigger ones and the top-down approach enumerates the bigger cliques efficiently in less time as compared to the depth-first search adopted by MULE. The MULE method takes relatively long time duration in case of higher threshold values because of the inbuilt redundancy and duplication.
Conclusion and future work
Finding coherent subgroups in graphs is a well-known research problem, especially when dealing with massive datasets. This work attempted to answer some of the most relevant questions in this domain. The problem of enumerating all maximal cliques is one of the elementary problems that identifies the dense substructures in large graphs. This paper presented an algorithm for the enumeration of all α-maximal cliques in an uncertain graph. The enumeration of all α-maximal cliques in an uncertain graph was carried out by applying three approaches. The proposed algorithms were tested against two recent methods using seven benchmark datasets. The algorithm performed better than the previous techniques by consuming 30% lesser time. The proposed method did not require to maintain any incremental change in the probabilities to enumerate cliques. Additionally, the cliques were enumerated in the decreasing order of sizes which assured the independence of larger maximal cliques on their smaller subsets. The worst case time complexity of the proposed technique was O(n2 n ). The experimental evaluation showed that the proposed method is 30% faster as compared to the other algorithms having same theoretical complexity. The future work can find its way towards the enumeration of other dense substructures like bicliques, quasi-cliques and k-cores in probabilistic graphs. In the field of bioinformatics, the researches usually need to forecast some fatal diseases in advance, on the basis of intra-functionalities of the genes expressed as probabilities. Keeping this thing in view, a new horizon of a research study can be limiting the probability factor for the enumeration of all α-maximal cliques of some specific size s.