اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدScaling Up Distanced-generalized Core Decomposition
70
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$-degree. The $h$-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$-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$-degree updating technique. Instead of recomputing the $h$-degrees, our algorithm can dynamically maintain the $h$-degrees for all vertices via exploring a very small subgraph, after peeling a vertex. We show that such an $h$-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 $hge 3$, our exact and sampling-based algorithms can achieve up to $10times$ and $100times$ speedup over the state-of-the-art algorithm, respectively.
قيم البحث
اقرأ أيضاً
Maintaining a $k$-core decomposition quickly in a dynamic graph is an important problem in many applications, including social network analytics, graph visualization, centrality measure computations, and community detection algorithms. The main chall
enge for designing efficient $k$-core decomposition algorithms is that a single change to the graph can cause the decomposition to change significantly. We present the first parallel batch-dynamic algorithm for maintaining an approximate $k$-core decomposition that is efficient in both theory and practice. Given an initial graph with $m$ edges, and a batch of $B$ updates, our algorithm maintains a $(2 + delta)$-approximation of the coreness values for all vertices (for any constant $delta > 0$) in $O(Blog^2 m)$ amortized work and $O(log^2 m loglog m)$ depth (parallel time) with high probability. Our algorithm also maintains a low out-degree orientation of the graph in the same bounds. We implemented and experimentally evaluated our algorithm on a 30-core machine with two-way hyper-threading on $11$ graphs of varying densities and sizes. Compared to the state-of-the-art algorithms, our algorithm achieves up to a 114.52x speedup against the best multicore implementation and up to a 497.63x speedup against the best sequential algorithm, obtaining results for graphs that are orders-of-magnitude larger than those used in previous studies. In addition, we present the first approximate static $k$-core algorithm with linear work and polylogarithmic depth. We show that on a 30-core machine with two-way hyper-threading, our implementation achieves up to a 3.9x speedup in the static case over the previous state-of-the-art parallel algorithm.
When analyzing temporal networks, a fundamental task is the identification of dense structures (i.e., groups of vertices that exhibit a large number of links), together with their temporal span (i.e., the period of time for which the high density hol
ds). In this paper we tackle this task by introducing a notion of temporal core decomposition where each core is associated with two quantities, its coreness, which quantifies how densely it is connected, and its span, which is a temporal interval: we call such cores emph{span-cores}. For a temporal network defined on a discrete temporal domain $T$, the total number of time intervals included in $T$ is quadratic in $|T|$, so that the total number of span-cores is potentially quadratic in $|T|$ as well. Our first main contribution is an algorithm that, by exploiting containment properties among span-cores, computes all the span-cores efficiently. Then, we focus on the problem of finding only the emph{maximal span-cores}, i.e., span-cores that are not dominated by any other span-core by both their coreness property and their span. We devise a very efficient algorithm that exploits theoretical findings on the maximality condition to directly extract the maximal ones without computing all span-cores. Finally, as a third contribution, we introduce the problem of emph{temporal community search}, where a set of query vertices is given as input, and the goal is to find a set of densely-connected subgraphs containing the query vertices and covering the whole underlying temporal domain $T$. We derive a connection between this problem and the problem of finding (maximal) span-cores. Based on this connection, we show how temporal community search can be solved in polynomial-time via dynamic programming, and how the maximal span-cores can be profitably exploited to significantly speed-up the basic algorithm.
In the decremental single-source shortest paths (SSSP) problem, the input is an undirected graph $G=(V,E)$ with $n$ vertices and $m$ edges undergoing edge deletions, together with a fixed source vertex $sin V$. The goal is to maintain a data structur
e that supports shortest-path queries: given a vertex $vin V$, quickly return an (approximate) shortest path from $s$ to $v$. The decremental all-pairs shortest paths (APSP) problem is defined similarly, but now the shortest-path queries are allowed between any pair of vertices of $V$. Both problems have been studied extensively since the 80s, and algorithms with near-optimal total update time and query time have been discovered for them. Unfortunately, all these algorithms are randomized and, more importantly, they need to assume an oblivious adversary. Our first result is a deterministic algorithm for the decremental SSSP problem on weighted graphs with $O(n^{2+o(1)})$ total update time, that supports $(1+epsilon)$-approximate shortest-path queries, with query time $O(|P|cdot n^{o(1)})$, where $P$ is the returned path. This is the first $(1+epsilon)$-approximation algorithm against an adaptive adversary that supports shortest-path queries in time below $O(n)$, that breaks the $O(mn)$ total update time bound of the classical algorithm of Even and Shiloah from 1981. Our second result is a deterministic algorithm for the decremental APSP problem on unweighted graphs that achieves total update time $O(n^{2.5+delta})$, for any constant $delta>0$, supports approximate distance queries in $O(loglog n)$ time; the algorithm achieves an $O(1)$-multiplicative and $n^{o(1)}$-additive approximation on the path length. All previous algorithms for APSP either assume an oblivious adversary or have an $Omega(n^{3})$ total update time when $m=Omega(n^{2})$.
Hardware accelerators (HAs) are essential building blocks for fast and energy-efficient computing systems. Accelerator Quick Error Detection (A-QED) is a recent formal technique which uses Bounded Model Checking for pre-silicon verification of HAs. A
-QED checks an HA for self-consistency, i.e., whether identical inputs within a sequence of operations always produce the same output. Under modest assumptions, A-QED is both sound and complete. However, as is well-known, large design sizes significantly limit the scalability of formal verification, including A-QED. We overcome this scalability challenge through a new decomposition technique for A-QED, called A-QED with Decomposition (A-QED$^2$). A-QED$^2$ systematically decomposes an HA into smaller, functional sub-modules, called sub-accelerators, which are then verified independently using A-QED. We prove completeness of A-QED$^2$; in particular, if the full HA under verification contains a bug, then A-QED$^2$ ensures detection of that bug during A-QED verification of the corresponding sub-accelerators. Results on over 100 (bugg
A new generalized inverse for a square matrix $Hinmathbb{C}^{ntimes n}$, called CCE-inverse, is established by the core-EP decomposition and Moore-Penrose inverse $H^{dag}$. We propose some characterizations of the CCE-inverse. Furthermore, two canon
ical forms of the CCE-inverse are presented. At last, we introduce the definitions of CCE-matrices and $k$-CCE matrices, and prove that CCE-matrices are the same as $i$-EP matrices studied by Wang and Liu in [The weak group matrix, Aequationes Mathematicae, 93(6): 1261-1273, 2019].
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
