Electrical closeness centrality is a classical and robust graph centrality measure. However, existing algorithms for computing electrical closeness centrality are often computationally expensive for large graphs, as they require determining the diagonal elements of the pseudo-inverse of the graph Laplacian matrix, denoted as$L^\dagger$. To address this challenge, we propose novel solutions for approximating$L^\dagger$by establishing a connection with the inverse of a Laplacian submatrix$L_{v}$, which is obtained by removing the$v$-th row and column from the original Laplacian matrix$L$. A key advantage of this connection is that$L_{v}^{-1}$admits various insightful combinatorial interpretations. Specifically, we present two novel interpretations of$L_{v}^{-1}$based on spanning trees and loop-erased random walks, which facilitate the development of efficient sampling algorithms. Building upon these theoretical insights, we introduce two algorithms for efficiently approximating electrical closeness centrality. We extensively evaluate the performance of our algorithms on five real-world datasets. Experimental results demonstrate that our approaches significantly outperform state-of-the-art methods by several orders of magnitude in both running time and estimation accuracy.

Identifying the maximum edge biclique in bipartite graphs, a complete bipartite subgraph with the largest number of edges, plays a crucial role in uncovering densely-connected communities and has significant applications in domains such as recommendation systems and biological network analysis. However, this problem is NP-hard, and existing methods face inefficiencies both in practice and theory. In this paper, we propose two novel algorithms with distinct branching strategies and provable time guarantees for solving the maximum edge biclique search problem. The first is a refined pivot-based branching algorithm that systematically exploits vertex adjacency relationships to bound the search for the maximum edge biclique, achieving a time complexity of O ( m 1.348 n ). The second is a cover-based algorithm that uncovers a novel duality between maximal bicliques and minimal vertex covers in bipartite graphs, attaining a complexity of O ( m 1.381 n ). To the best of our knowledge, these two algorithms achieve the best-known worst-case time complexities for this problem. Notably, while the cover-based algorithm has a marginally higher theoretical complexity, it typically provides superior practical performance on dense graphs due to its inherent pruning efficiency. To further enhance performance, we introduce advanced pruning techniques, including polynomial-time solvable graph cases, neighbor and non-neighbor constraint-based upper bounds, vertex cover constraint-driven upper bounds, heuristic prioritization, and an improved progressive bounding approach. Additionally, we propose a hybrid framework that deploys the pivot-based approach for sparse graph regions and the cover-based approach for dense regions, balancing efficiency across varying graph structures. Extensive experiments on 12 real-world bipartite graphs demonstrate that our hybrid framework outperforms the state-of-the-art baseline by up to four orders of magnitude and achieves speedups of several times to orders of magnitude over the pivot-based approach on dense graphs.

Cohesive sub graph mining has received much at-tention in the area of graph analysis. A k- truss, defined as a sub graph where each edge is associated with at least$k-2$triangles, serves as a fundamental graph analysis tool. Among all k-trusses, the$k_{\max}$-truss with the maximum$k$value holds significant importance in various practical applications such as community search and keyword retrieval. Furthermore, it is also closely related to many graph analysis problems, particularly those computational complexity problems parameterized by$k$. However, real-world graphs often exhibit large-scale characteris-tics, making it impractical to fully load them into main memory. In this paper, we investigate the problem of finding the$k_{\max}$-truss in external memory settings. To address this problem, we propose an 110 efficient algorithm following a semi-external model, which only allows node information to be loaded into main memory. Our approach leverages greedy strategies and a binary search framework to efficiently find the$k_{\max}$- truss. Subsequently, an elegant data structure is proposed to significantly reduce 110 costs. Furthermore, to address dynamic graph updates, we develop an 110 efficient$k_{\max}$- truss maintenance algorithm based on the local-first update technique. To evaluate the performance of our algorithms, we conduct extensive experiments. The results demonstrate the high efficiency and scalability of our algorithms, which are at least two orders of magnitude faster in runtime and at least one order of magnitude lower in terms of 110 costs compared to the state-of-the-art solutions.

A k-biplex is an induced subgraph of a bipartite graph which requires every vertex on the one side disconnecting at most k vertices on the other side. Enumerating all maximal k-biplexes in a bipartite graph is a fundamental operator in bipartite graph analysis and finds applications in various domains, including community detection, online recommendation, and fraud detection in finance networks. The state-of-the-art solutions for maximal k-biplex enumeration suffer from efficiency issues as k increases (k ≥ 2), with the time complexity of O(m 2 n ), where n (m) denotes the number of vertices (edges) in the bipartite graph. To address this issue, we propose two theoretically and practically efficient enumeration algorithms based on novel branching techniques. Specifically, we first devise a new branching rule as a fundamental component. Building upon this, we then develop a novel branch-and-bound enumeration algorithm to efficiently enumerate maximal k-biplexes. We prove that our algorithm achieves a worst-case time complexity of O(mα k n ), where α k < 2, thus significantly improving the time complexity compared to previous algorithms. To enhance the performance, we further propose an improved enumeration algorithm based on a novel pivot-based branching rule. Theoretical analysis reveals that our improved algorithm has a time complexity of O(mβ k n ), where β k is strictly less than α k . In addition, we also present several non-trivial optimization techniques, including graph reduction, upper-bounds based pruning, and ordering-based optimization, to further improve the efficiency of our algorithms. Finally, we conduct extensive experiments on 6 large real-world bipartite graphs to evaluate the efficiency and scalability of the proposed solutions. The results demonstrate that our improved algorithm achieves up to 5 orders of magnitude faster than the state-of-the-art solutions.

The study of k -defective cliques, defined as induced subgraphs that differ from cliques by at most k missing edges, has attracted much attention in graph analysis due to their relevance in various applications, including social network analysis and implicit interaction predictions. However, determining the maximum k -defective clique in graphs has been proven to be an NP-hard problem, presenting significant challenges in finding an efficient solution. To address this problem, we develop a theoretically and practically efficient algorithm that leverages newly-designed branch reduction rules and a pivot-based branching technique. Our analysis establishes that the time complexity of the proposed algorithm is bounded by O(mγ k n ), where γ k is a real value strictly less than 2 (e.g., when k= 1, 2, and 3, γ k = 1.466, 1.755, and 1.889, respectively). To our knowledge, this algorithm achieves the best worst-case time complexity to date compared to state-of-the-art solutions. Moreover, to further reduce unnecessary branches, we propose a time-efficient upper bound-based pruning technique, which is obtained by manipulating information such as the number of distinct colors assigned to vertices and the presence of non-neighbors among them. Additionally, we employ an ordering-based heuristic approach as a preprocessing step to improve computational efficiency. Finally, we conduct extensive experiments on a diverse set of over 300 graphs to evaluate the efficiency of the proposed solutions. The results demonstrate that our algorithm achieves a speedup of 3 orders of magnitude over state-of-the-art solutions in processing most of real-world graphs.

Effective resistance (ER) is a fundamental metric for measuring node similarities in a graph, and it finds applications in various domains including graph clustering, recommendation systems, link prediction, and graph neural networks. The state-of-the-art algorithm for computing effective resistance relies on a landmark technique, which involves selecting a node that is easy to reach by all the other nodes as a landmark. The performance of this technique heavily depends on the chosen landmark node. However, in many real-life graphs, it is not always possible to find an easily reachable landmark node, which can significantly hinder the algorithm's efficiency. To overcome this problem, we propose a novel multiple landmarks technique which involves selecting a set of landmark nodes V l such that the other nodes in the graph can easily reach any one of a landmark node in V l . Specifically, we first propose several new formulas to compute ER with multiple landmarks, utilizing the concept of Schur complement. These new formulas allow us to pre-compute and maintain several small-sized matrices related to V l as a compact index. With this powerful index technique, we demonstrate that both single-pair and single-source ER queries can be efficiently answered using a newly-developed V l -absorbed random walk sampling or V l -absorbed push technique. Comprehensive theoretical analysis shows that all proposed index-based algorithms achieve provable performance guarantees for both single-pair and single-source ER queries. Extensive experiments on 5 real-life datasets demonstrate the high efficiency of our multiple landmarks-based index techniques. For instance, our algorithms, with a 1.5 GB index size, can be up to 4 orders of magnitude faster than the state-of-the-art algorithms while achieving the same accuracy on a large road network.

$K$-clique counting is a fundamental problem in network analysis which has attracted much attention in recent years. Computing the count of$k$-cliques in a graph for a large$k$(e.g.,$k=8$) is often intractable as the number of$k$-cliques increases exponentially w.r.t. (with respect to)$k$. Existing exact$k$-clique counting algorithms are often hard to handle large dense graphs, while sampling-based solutions either require a huge number of samples or consume very high storage space to achieve a satisfactory accuracy. To overcome these limitations, we propose a new framework to estimate the number of$k$-cliques which integrates both the exact$k$-clique counting technique and three novel color-based sampling techniques. The key insight of our framework is that we only apply the exact algorithm to compute the$k$-clique counts in thesparse regionsof a graph, and use the proposed color-based sampling approaches to estimate the number of$k$-cliques in thedense regionsof the graph. Specifically, we develop three novel dynamic programming based$k$-color set sampling techniques to efficiently estimate the$k$-clique counts, where a$k$-color set contains$k$nodes with$k$different colors. Since a$k$-color set is often a good approximation of a$k$-clique in the dense regions of a graph, our sampling-based solutions are extremely efficient and accurate. Moreover, the proposed sampling techniques are space efficient which use near-linear space w.r.t. graph size. We conduct extensive experiments to evaluate our algorithms using 8 real-life graphs. The results show that our best algorithm is at least one order of magnitude faster than the state-of-the-art sampling-based solutions (with the same relative error 0.1%) and can be up to three orders of magnitude faster than the state-of-the-art exact algorithm on large graphs.

Maximal clique enumeration is a fundamental operator in graph analysis. The model of clique, however, is typically too restrictive for real-world applications as it requires an edge for every pair of vertices. To remedy this restriction, practical graph analysis applications often resort to find relaxed cliques as alternatives. In this work, we investigate a notable relaxed clique model, called s-defective clique, which allows at most s edges to be missing. Similar to the complexity of maximal clique enumeration, the problem of enumerating all maximal s-defective cliques is also NP-hard. To solve this problem, we first develop a new polynomial-delay algorithm based on a carefully-designed reverse search technique, which can output two consecutive results within polynomial time. To achieve better practical efficiency, we propose a branch-and-bound algorithm with a novel pivoting technique. We prove that the time complexity of this algorithm depends only on O(α_sn) or O(αsδ) when using a degeneracy ordering optimization, where αs is a positive real number strictly less than 2, and δ (δ 0). We also develop several new pruning techniques to further improve the efficiency of our branch-and-bound algorithm to enumerate all relatively-large maximal s-defective cliques. In addition, we further generalize our pivot-based branch-and-bound algorithm to enumerate all maximal subgraphs satisfying a hereditary property. Here we call a graph meeting the hereditary property if all its subgraphs have the same property as itself. Finally, extensive experiments on 11 datasets demonstrate the efficiency, effectiveness, and scalability of the proposed solutions.

Finding cohesive subgraphs from a bipartite graph is a fundamental operator in bipartite graph analysis. In this paper, we focus on the problem of mining cohesive subgraphs from a bipartite graph that satisfy a hereditary property. Here a cohesive subgraph meets the hereditary property if all of its subgraphs satisfy the same property as itself. We show that several important cohesive subgraph models, such as maximal biclique and maximal k-biplex, satisfy the hereditary property. The problem of enumerating all maximal hereditary subgraphs was known to be NP-hard. To solve this problem, we first propose a novel and general pivot-based enumeration framework to efficiently enumerate all maximal hereditary subgraphs in a bipartite graph. Then, based on our general framework, we develop a new pivot-based algorithm with several pruning techniques to enumerate all maximal bicliques. We prove that the worst-case time complexity of our pivot-based maximal biclique enumeration algorithm is O(m x 2n/2 ) (or O(m\times 1.414^n)) which is near optimal since there exist up to O(2n/2 ) maximal bicliques in a bipartite graph with n vertices and m edges. Moreover, we also show that our algorithm can achieve polynomial-delay time complexity with a slight modification. Third, on the basis of our general framework, we also devise a novel pivot-based algorithm with several non-trivial pruning techniques to enumerate maximal k-biplexes in a bipartite graph. Finally, we conduct extensive experiments using 11 real-world bipartite graphs to evaluate the proposed algorithms. The results show that our pivot-based solutions can achieve one order of magnitude (three orders of magnitude) faster than the state-of-the-art maximal biclique enumeration algorithms (maximal k-biplex enumeration algorithms).

Resistance distance is a fundamental metric to measure the similarity between two nodes in graphs which has been widely used in many real-world applications. In this paper, we study two problems on approximately computing resistance distance: (i) single-pair query which aims at calculating the resistance distance r(s, t) for a given pair of nodes (s, t); and (ii) single-source query which is to compute all the resistance distances r(s, u) for all nodes u in the graph with a given source node s. Existing algorithms for these two resistance distance query problems are often costly on large graphs. To efficiently solve these problems, we first establish several interesting connections among resistance distance, a new concept called v-absorbed random walk, random spanning forests, and a newly-developed v-absorbed push procedure. Based on such new connections, we propose three novel and efficient sampling-based algorithms as well as a deterministic algorithm for single-pair query; and we develop an online and two index-based approximation algorithms for single-source query. We show that the two index-based algorithms for single-source query take almost the same running time as the algorithms for single-pair query with the aid of a linear-size index. The striking feature of all our algorithms is that they are allowed to select an easy-to-hit node by random walks on the graph. Such an easy-to-hit landmark node v can make the v-absorbed random walk sampling, spanning tree sampling, as well as the v-absorbed push more efficient, thus significantly improving the performance of our algorithms. Extensive experiments on 5 real-life datasets show that our algorithms substantially outperform the state-of-the-art algorithms for two resistance distance query problems in terms of both running time and estimation errors.

Personalized PageRank (PPR) computation is a fundamental problem in graph analysis. The state-of-the-art algorithms for PPR computation are based on a bidirectional framework which include a deterministic forward push and a Monte Carlo sampling procedure. The Monte Carlo sampling procedure, however, often has a relatively-large variance, thus reducing the performance of the PPR computation algorithms. To overcome this issue, we develop two novel variance-reduced Monte Carlo techniques for PPR computation. Our first technique is to apply power iterations to reduce the variance of the Monte Carlo sampling procedure. We prove that conducting few power iterations can significantly reduce the variance of existing Monte Carlo estimators, only with few additional costs. Moreover, we show that such a simple and novel variance-reduced Monte Carlo technique can achieve comparable estimation accuracy and the same time complexity as the state-of-the-art bidirectional algorithms. Our second technique is a novel progressive sampling method which uses the historical information of former samples to reduce the variance of the Monte Carlo estimator. We develop several novel PPR computation algorithms by integrating both of these variance reduction techniques with two existing Monte Carlo sampling approaches, including random walk sampling and spanning forests sampling. Finally, we conduct extensive experiments on 5 real-life large graphs to evaluate our solutions. The results show that our algorithms can achieve much higher PPR estimation accuracy by using much less time, compared to the state-of-the-art bidirectional algorithms.

A (p,q)-biclique is a complete subgraph (X,Y) that |X|=p, |Y|=q. Counting (p,q)-bicliques in bipartite graphs is an important operator for many bipartite graph analysis applications. However, getting the count of (p,q)-bicliques for large p and q (e.g., p,q ≥ 10) is extremely difficult, because the number of (p,q)-bicliques increases exponentially with respect to p and q. The state-of-the-art algorithm for this problem is based on the (p,q)-biclique enumeration technique which is often costly due to the exponential blowup in the enumeration space of (p,q)-bicliques. To overcome this problem, we first propose a novel exact algorithm, called EPivoter, based on a newly-developed edge-pivoting technique. The striking feature of EPivoter is that it can count (p,q)-bicliques for all pairs of (p,q) using a combinatorial technique, instead of exhaustively enumerating all (p,q)-bicliques. Second, we propose a novel dynamic programming (DP) based h-zigzag sampling technique to provably approximate the count of the (p,q)-bicliques for all pairs of (p,q), where an h-zigzag is an ordered simple path in G with length 2h-1 (h = min{p,q}). We show that our DP-based sampling technique is very efficient. Third, to further improve the efficiency, we also propose a hybrid framework that integrates both the exact EPivoter algorithm and sampling-based algorithms. Extensive experiments on 7 real-world graphs show that our algorithms are several orders of magnitude faster than the state-of-the-art algorithm.

Core decomposition on uncertain graphs is a fundamental problem in graph analysis. Given an uncertain graph G, the core decomposition problem is to determine all (k, \eta)-cores in G, where a (k, \eta)-core is a maximal subgraph of G such that each node has an \eta-degree no less than k within the subgraph. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes nodes with the smallest \eta-degrees and also dynamically updates their neighbors' \eta-degrees. Unfortunately, we find that such a peeling algorithm with the dynamical \eta-degree updating technique is incorrect due to the inaccuracy of the recursive floating-point number division operations involved in the dynamical updating procedure. To solve this problem, we propose a bottom-up algorithm based on an on-demand computational strategy. To further improve the efficiency, we also develop a more-efficient top-down algorithm with several nontrivial optimization techniques. Both of our algorithms do not involve any floating-point number division operations, thus the correctness can be guaranteed. We conduct extensive experiments to evaluate our algorithms using five large real-life datasets. The results show that our algorithms are at least three orders of magnitude faster than the existing exact algorithms on large uncertain graphs.

Finding all maximal k-plexes on networks is a fundamental research problem in graph analysis due to many important applications, such as community detection, biological graph analysis, and so on. A k-plex is a subgraph in which every vertex is adjacent to all but at most k vertices within the subgraph. In this paper, we study the problem of enumerating all large maximal k-plexes of a graph and develop several new and efficient techniques to solve the problem. Specifically, we first propose several novel upper-bounding techniques to prune unnecessary computations during the enumeration procedure. We show that the proposed upper bounds can be computed in linear time. Then, we develop a new branch-and-bound algorithm with a carefully-designed pivot re-selection strategy to enumerate all k-plexes, which outputs all k-plexes in O(n2?k n) time theoretically, where n is the number of vertices of the graph and ? k is strictly smaller than 2. In addition, a parallel version of the proposed algorithm is further developed to scale up to process large real-world graphs. Finally, extensive experimental results show that the proposed sequential algorithm can achieve up to 2× to 100× speedup over the state-of-the-art sequential algorithms on most benchmark graphs. The results also demonstrate the high scalability of the proposed parallel algorithm. For example, on a large real-world graph with more than 200 million edges, our parallel algorithm can finish the computation within two minutes, while the state-of-the-art parallel algorithm cannot terminate within 24 hours.

Core decomposition on uncertain graphs is shown to be a key problem in graph analysis. However, existing algorithms for solving this problem are based on a peeling algorithm with the dynamically updating technique, which can lead to relatively large errors due to the inaccuracy of the recursive floating-point number division operations. In this paper, we first develop two novel algorithms, a bottom-up approach and a top-down approach, which do not involve any floating-point number division operations to guarantee correctness. Then, we develop a parallel version for each approach to deal with large graphs. Extensive experimental results evidence the efficiency, effectiveness, and scalability of our proposed algorithms.

Maximal clique enumeration on uncertain graphs is a fundamental problem in uncertain graph analysis. In this paper, we study a problem of enumerating all maximal (k,n)-cliques on an uncertain graph G, where a vertex set H of G is a maximal (k,n)-clique if (1) H (|H| ≥ k) is a clique with probability no less than n, and (2) H is a maximal vertex set satisfying (1). The state-of-the-art algorithms for enumerating all maximal (k,n)-cliques are based on a set enumeration technique which are often very costly. This is because the set enumeration based techniques may explore all subsets of a maximal (k,n)-clique, thus resulting in many unnecessary computations. To overcome this issue, we propose several novel and efficient pivot-based algorithms to enumerate all maximal (k,n)-cliques based on a newly-developed pivot-based pruning principle. Our pivot-based pruning principle is very general which can be applied to speed up the enumeration of any maximal subgraph that satisfies a hereditary property. Here the hereditary property means that if a maximal subgraph H satisfies a property P, any subgraph of H also meets P. To the best of our knowledge, our work is the first to systematically explore the idea of pivot for maximal clique enumeration on uncertain graphs. In addition, we also develop a nontrivial size-constraint based pruning technique and a new graph reduction technique to further improve the efficiency. Extensive experiments on nine real-world graphs demonstrate the efficiency, effectiveness, and scalability of the proposed algorithms.

Computing the personalized PageRank vector is a fundamental problem in graph analysis. In this paper, we propose several novel algorithms to efficiently compute the personalized PageRank vector with a decay factor α based on an interesting connection between the personalized PageRank values and the weights of random spanning forests of the graph. Such a connection is derived based on a newly-developed matrix forest theorem on graphs. Based on this, we present an efficient spanning forest sampling algorithm via simulating loop-erased α-random walks to estimate the personalized PageRank vector. Compared to all existing methods, a striking feature of our approach is that its performance is insensitive w.r.t. (with respect to) the parameter α. As a consequence, our algorithm is often much faster than the state-of-the-art algorithms when α is small, which is the demanding case for many graph analysis tasks. We show that our technique can significantly improve the efficiency of the state-of-the-art algorithms for answering two well-studied personalized PageRank queries, including single source query and single target query. Extensive experiments on seven large real-world graphs demonstrate the efficiency of the proposed method.

K-clique counting is a fundamental problem in network analysis which has attracted much attention in recent years. Computing the count of k-cliques in a graph for a large k (e.g., k = 8) is often intractable as the number of k-cliques increases exponentially w.r.t. (with respect to) k. Existing exact k-clique counting algorithms are often hard to handle large dense graphs, while sampling-based solutions either require a huge number of samples or consume very high storage space to achieve a satisfactory accuracy. To overcome these limitations, we propose a new framework to estimate the number of k-cliques which integrates both the exact k-clique counting technique and two novel color-based sampling techniques. The key insight of our framework is that we only apply the exact algorithm to compute the k-clique counts in the sparse regions of a graph, and use the proposed sampling-based techniques to estimate the number of k-cliques in the dense regions of the graph. Specifically, we develop two novel dynamic programming based k-color set sampling techniques to efficiently estimate the k-clique counts, where a k-color set contains k nodes with k different colors. Since a k-color set is often a good approximation of a k-clique in the dense regions of a graph, our sampling-based solutions are extremely efficient and accurate. Moreover, the proposed sampling techniques are space efficient which use near-linear space w.r.t. graph size. We conduct extensive experiments to evaluate our algorithms using 8 real-life graphs. The results show that our best algorithm is at least one order of magnitude faster than the state-of-the-art sampling-based solutions (with the same relative error 0.1%) and can be up to three orders of magnitude faster than the state-of-the-art exact algorithm on large graphs.

Core decomposition is a fundamental operator in network analysis. In this paper, we study a problem of computing distance-generalized core decomposition on a network. A distance-generalized core, also termed (k, h)-core, is a maximal subgraph in which every vertex has at least k other vertices at distance no larger than h. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes the vertex (denoted by v) from the graph that has the smallest h-hop degree. The h-hop degree of a vertex v denotes the number of other vertices that are reachable from v within h hops. Such a peeling algorithm, however, needs to frequently recompute the h-hop degrees of v's neighbors after deleting v, which is typically very costly for a large h. To overcome this limitation, we propose an efficient peeling algorithm based on a novel h-hop degree updating technique. Instead of recomputing the h-hop degrees, our algorithm can dynamically maintain the h-hop degrees for all vertices via exploring a very small subgraph, after peeling a vertex. We show that such an h-hop degree updating procedure can be efficiently implemented by an elegant bitmap technique. In addition, we also propose a sampling-based algorithm and a parallelization technique to further improve the efficiency. Finally, we conduct extensive experiments on 12 real-world graphs to evaluate our algorithms. The results show that, when h≥3, our exact and sampling-based algorithms can achieve up to 10x and 100x speedup over the state-of-the-art algorithm, respectively.

Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict, respectively. We propose a novel model, called maximal (a, k)-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal (α, k)-clique is a clique in which every node has at most k negative neighbors and at least ⌈ak⌉ positive neighbors (α ≥ 1). We show that the problem of enumerating all maximal (a, k)-cliques in a signed network is NP-hard. To enumerate all maximal (a, k)-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal (a, k)-cliques in the reduced signed network. In addition, we also propose an efficient algorithm with three novel upper-bounding techniques to find the maximum (a, k)-clique in a signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Enumerating maximal cliques from an uncertain graph is a fundamental problem in uncertain graph analysis. Given an uncertain graph G, a set of nodes C in G is a maximal (k, τ)-clique if (1) |C|>k and C is a clique with probability at least τ, and (2) C is a maximal node set meeting (1). The state-of-the-art algorithm for enumerating all maximal (k, τ)-cliques is very costly when handling large uncertain graphs, as its time complexity is proportional to 2^n where n is the number of nodes in the uncertain graph. To overcome this issue, we propose two new core-based pruning algorithms to reduce the uncertain graph size without missing any maximal (k, τ)-clique. We also develop a novel cut-based optimization technique to further improve the pruning performance of the core-based pruning algorithms. Based on these pruning techniques, we propose an improved algorithm to enumerate all maximal (k, τ)-cliques, and a new algorithm with several novel upper-bounding techniques to compute one of maximum (k, τ)-cliques from the pruned uncertain graph. The results of extensive experiments on six real-world datasets demonstrate the efficiency and effectiveness of the proposed algorithms.

Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict respectively. We propose a novel model, called maximal (α, k)-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal (α, k)-clique is a clique in which every node has at most. negative neighbors and at least [αk] positive neighbors (α ≥ 1). We show that the problem of enumerating all maximal (α, k)- cliques in a signed network is NP-hard. To enumerate all maximal (α,k)-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal (α,k)-cliques in the reduced signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Community search is a fundamental graph mining task. Unfortunately, most previous community search studies focus mainly on identifying communities in a network without temporal information. In this paper, we study the problem of finding persistent communities in a temporal network, in which every edge is associated with a timestamp. Our goal is to identify the communities that are persistent over time. To this end, we propose a novel persistent community model called (θ,τ) community. We prove that the problem of identifying the maximum (θ,τ) persistent k-core is NP-hard. To solve this problem, we propose a novel branch and bound algorithm with several carefully-designed pruning rules to find the maximum (θ,τ)-persistent. We conduct k-cores efficiently. We conduct extensive experiments in several real-world temporal networks. The results demonstrate the efficiency, scalability, and effectiveness of the proposed solutions.