Cliques refer to subgraphs in an undirected graph such that vertices in each subgraph are pairwise adjacent. The maximum clique problem, to find the clique with most vertices in a given graph, has been extensively studied. Besides its theoretical value as an NP-hard problem, the maximum clique problem is known to have direct applications in various fields, such as community search in social networks and social media, team formation in expert networks, gene expression and motif discovery in bioinformatics and anomaly detection in complex networks, revealing the structure and function of networks. However, algorithms designed for the maximum clique problem are expensive to deal with real-world networks. In this paper, we first devise a randomized algorithm for the maximum clique problem. Different from previous algorithms that search from each vertex one after another, our approachRMC, for the randomized maximum clique problem, employs a binary search while maintaining a lower bound$\underline{\omega _c}$and an upper bound$\overline{\omega _c}$of$\omega (G)$. In each iteration,RMCattempts to find a$\omega _t$-clique where$\omega _t=\lfloor (\underline{\omega _c}+\overline{\omega _c})/2\rfloor$. As finding$\omega _t$in each iteration is NP-complete, we extract a seed set$S$such that the problem of finding a$\omega _t$-clique in$G$is equivalent to finding a$\omega _t$-clique in$S$with probability guarantees ($\geq$$ 1-n^{-c}$). We propose a novel iterative algorithm to determine the maximum clique by searching a$k$-clique in$S$starting from$k=\underline{\omega _c}+1$until$S$becomes$\lbrace \rbrace$, when more iterations benefit marginally. Due to the potential inconsistency of maximum clique algorithms, we study the problem of maximum clique enumeration and propose an efficient algorithmRMCEto enumerate all maximum cliques in a given graph. As confirmed by the experiments, bothRMCandRMCEare much more efficient and robust than previous solutions,RMCcan always find the exact maximum clique, andRMCEcan always enumerate all maximum cliques in a given graph.

Triadic closure is ubiquitous in social networks, which refers to the property among three individuals, A, B, and C, such that if there exist strong ties between A-B and A-C, then there must be a strong or weak tie between B-C. Related to triadic closure, the number of triangles has been extensively studied since it can be effectively used as a metric to analyze the structure and function of a network. In this paper, from a different viewpoint, we study triangle-free dense structures which have received little attention. We focus on$K_{3,3}$where there are two subsets of three vertices, a vertex in a subset has an edge connected to every vertex in another subset while it does not have an edge to any other vertex in the same subset. Such$K_{n,n}$in general implies a philosophy contradiction: (a) Any two individuals are friends if they have no common friends, and (b) Any two individuals are not friends if they have common friends. However, we find such induced$K_{3,3}$does exist frequently, and they do not disappear over time over a real academic collaboration network. In addition, in the real datasets tested, nearly all edges appearing in$K_{3,3}$appear in some triangles. We analyze the expected numbers of induced$K_{3,3}$and triangles ($\Delta$) in four representative random graph models, namely, Erdős-Rényi random graph model, Watts-Strogatz small-world model, Barabási-Albert preferential attachment model, and configuration model, and give an algorithm to enumerate all distinct$K_{3,3}$in an undirected social network. We conduct extensive experiments on both real and synthetic datasets to confirm our findings. As an application, such$K_{3,3}$found helps to find new stars collaborated by well-known figures who themselves do not collaborate.

String similarity search is a fundamental query that has been widely used for DNA sequencing, error-tolerant query autocompletion, and data cleaning needed in database, data warehouse, and data mining. In this paper, we study string similarity search based on edit distance that is supported by many database management systems such as Oracle and PostgreSQL. Given the edit distance, ed(s, t), between two strings, s and t, the string similarity search is to find every string t in a string database D which is similar to a query string s such that ed(s, t) ≤ τ for a given threshold τ. In the literature, most existing work takes a filter-and-verify approach, where the filter step is introduced to reduce the high verification cost of two strings by utilizing an index built offline for D. The two up-to-date approaches are prefix filtering and local filtering. In this paper, we study string similarity search where strings can be either short or long. Our approach can support long strings, which are not well supported by the existing approaches due to the size of the index built and the time to build such index. We propose two new hash-based labeling techniques, named OX label and XX label, for string similarity search. We assign a hash-label, Hs, to a string s, and prune the dissimilar strings by comparing two hash-labels, Hsand Ht, for two strings s and t in the filter step. The key idea is to take the dissimilar bit-patterns between two hash-labels. We discuss our hash-based approaches, address their pruning power, and give the algorithms. Our hash-based approaches achieve high efficiency, and keep its index size and index construction time one order of magnitude smaller than the existing approaches in our experiment at the same time.

Answering reachability queries is one of the fundamental graph operations. The existing approaches build indexes and answer reachability queries on a directed acyclic graph (DAG) G, which is constructed by coalescing each strongly connected component of the given directed graph G into a node of G. Considering that G can still be large to be processed efficiently, there are studies to further reduce G to a smaller graph. However, these approaches suffer from either inefficiency in answering reachability queries, or cannot scale to large graphs.

Cliques refer to subgraphs in an undirected graph such that vertices in each subgraph are pairwise adjacent. The maximum clique problem, to find the clique with most vertices in a given graph, has been extensively studied. Besides its theoretical value as an NP-hard problem, the maximum clique problem is known to have direct applications in various fields, such as community search in social networks and social media, team formation in expert networks, gene expression and motif discovery in bioinformatics and anomaly detection in complex networks, revealing the structure and function of networks. However, algorithms designed for the maximum clique problem are expensive to deal with real-world networks. In this paper, we devise a randomized algorithm for the maximum clique problem. Different from previous algorithms that search from each vertex one after another, our approach RMC , for the randomized maximum clique problem, employs a binary search while maintaining a lower bound ω c and an upper bound [EQUATION] of ω ( G ). In each iteration, RMC attempts to find a ω t -clique where [EQUATION]. As finding ω t in each iteration is NP-complete, we extract a seed set S such that the problem of finding a ω t -clique in G is equivalent to finding a ω t -clique in S with probability guarantees (≥1− n −c ). We propose a novel iterative algorithm to determine the maximum clique by searching a k -clique in S starting from k = ω c +1 until S becomes [EQUATION], when more iterations benefit marginally. As confirmed by the experiments, our approach is much more efficient and robust than previous solutions and can always find the exact maximum clique.

As an important graph operator, reachability query has been extensively studied over decades, which is to check whether a vertex can reach another vertex over a large directed graph G with n vertices and m edges. The efforts made in the reported studies have greatly improved the query time of answering reachability queries online, while reducing the offline index construction time to construct an index with a reasonable size given the approach taken, where an entry in an index for a vertex is called a label of the vertex. Among all the work, the recent development of IP (Independent Permutation) employs randomness using k-min-wise independent permutations to process reachability queries, and shows the advantages for both query time and index construction time. In this paper, we propose a new Bloom filter Labeling, denoted as BFL. We show that the probability to answer reachability queries by BFL can be bounded, and BFL has high pruning power to answer more reachability queries directly. We give algorithms and analyze the pruning power of BFL. We conduct extensive studies using 19 large datasets. We show that BFL with an interval label performs best in the index construction time for all 19 cases, and performs best in query time for 16 out of 19 cases.

The CPU cache performance is one of the key issues to efficiency in database systems. It is reported that cache miss latency takes a half of the execution time in database systems. To improve the CPU cache performance, there are studies to support searching including cache-oblivious, and cache-conscious trees. In this paper, we focus on CPU speedup for graph computing in general by reducing the CPU cache miss ratio for different graph algorithms. The approaches dealing with trees are not applicable to graphs which are complex in nature.

Social hierarchy (i.e., pyramid structure of societies) is a fundamental concept in sociology and social network analysis. The importance of social hierarchy in a social network is that the topological structure of the social hierarchy is essential in both shaping the nature of social interactions between individuals and unfolding the structure of the social networks. The social hierarchy found in a social network can be utilized to improve the accuracy of link prediction, provide better query results, rank web pages, and study information flow and spread in complex networks. In this paper, we model a social network as a directed graph$G$, and consider the social hierarchy as DAG (directed acyclic graph) of$G$, denoted as$G_D$. By DAG, all the vertices in$G$can be partitioned into different levels, the vertices at the same level represent a disjoint group in the social hierarchy, and all the edges in DAG follow one direction. The main issue we study in this paper is how to find DAG$G_D$in$G$. The approach we take is to find$G_D$by removing all possible cycles from$G$such that$G = {\cal U}(G) \cup G_D$, where${\cal U}(G)$is a maximum Eulerian subgraph which contains all possible cycles. We give the reasons for doing so, investigate the properties of$G_D$found, and discuss the applications. In addition, we develop a novel two-phase algorithm, called Greedy-&-Refine, which greedily computes an Eulerian subgraph and then refines this greedy solution to find the maximum Eulerian subgraph. We give a bound between the greedy solution and the optimal. The quality of our greedy approach is high. We conduct comprehensive experimental studies over 14 real-world datasets. The results show that our algorithms are at least two orders of magnitude faster than the baseline algorithm.

Reachability query is a fundamental graph operation which answers whether a vertex can reach another vertex over a large directed graph G with n vertices and m edges, and has been extensively studied. In the literature, all the approaches compute a label for every vertex in a graph G by index construction offline. The query time for answering reachability queries online is affected by the quality of the labels computed in index construction. The three main costs are the index construction time, the index size, and the query time. Some of the up-to-date approaches can answer reachability queries efficiently, but spend non-linear time to construct an index. Some of the up-to-date approaches construct an index in linear time and space, but may need to depth-first search G at run-time in O ( n + m ). In this paper, as the first, we propose a new randomized labeling approach to answer reachability queries, and the randomness is by independent permutation. We conduct extensive experimental studies to compare with the up-to-date approaches using 19 large real datasets used in the existing work and synthetic datasets. We confirm the efficiency of our approach.