We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some e...
详细信息
ISBN:
(纸本)9780769551357
We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the out-going and incoming adjacency lists of the vertices appear in non-decreasing order of weight. (Spira's algorithm makes the same assumption about the out-going adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on n vertices with independent exponential edge weights is O(n), with very high probability. This improves on the previously best result of O(n log n), which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with independent exponential edge weights is O(n 2), matching a recent result of Peres et al. Furthermore, the probability that the new algorithm requires more than O(n 2) time is exponentially small, improving on the polynomially small probability of Peres et al.
In this paper, we present a method for detecting malicious activity within networks of interest. We leverage prior community detection work by propagating threat probabilities across graph nodes, given an initial set ...
详细信息
ISBN:
(纸本)9781479903566
In this paper, we present a method for detecting malicious activity within networks of interest. We leverage prior community detection work by propagating threat probabilities across graph nodes, given an initial set of known malicious nodes. We enhance prior work by employing constraints which remove the adverse effect of cyclic propagation that is a byproduct of current methods. We demonstrate the effectiveness of Probabilistic Threat Propagation on the task of detecting malicious web destinations.
With the rise of social networks, large-scale graph analysis becomes increasingly important. Because SQL lacks the expressiveness and performance needed for graph algorithms, lower-level, general-purpose languages are...
详细信息
ISBN:
(纸本)9781467349093;9781467349086
With the rise of social networks, large-scale graph analysis becomes increasingly important. Because SQL lacks the expressiveness and performance needed for graph algorithms, lower-level, general-purpose languages are often used instead. For greater ease of use and efficiency, we propose SociaLite, a high-level graph query language based on Datalog. As a logic programming language, Datalog allows many graph algorithms to be expressed succinctly. However, its performance has not been competitive when compared to low-level languages. With SociaLite, users can provide high-level hints on the data layout and evaluation order;they can also define recursive aggregate functions which, as long as they are meet operations, can be evaluated incrementally and efficiently. We evaluated SociaLite by running eight graph algorithms (shortest paths, PageRank, hubs and authorities, mutual neighbors, connected components, triangles, clustering coefficients, and betweenness centrality) on two real-life social graphs, Live-Journal and Last. fm. The optimizations proposed in this paper speed up almost all the algorithms by 3 to 22 times. SociaLite even outperforms typical Java implementations by an average of 50% for the graph algorithms tested. When compared to highly optimized Java implementations, SociaLite programs are an order of magnitude more succinct and easier to write. Its performance is competitive, giving up only 16% for the largest benchmark. Most importantly, being a query language, SociaLite enables many more users who are not proficient in software engineering to make social network queries easily and efficiently.
Betweenness centrality is a graph analytic that states the importance of a vertex based on the number of shortest paths that it is on. As such, betweenness centrality is a building block for graph analysis tools and i...
详细信息
Betweenness centrality is a graph analytic that states the importance of a vertex based on the number of shortest paths that it is on. As such, betweenness centrality is a building block for graph analysis tools and is used by many applications, including finding bottlenecks in communication networks and community detection. Computing betweenness centrality is computation- ally demanding, O ( V 2 + V · E ) (for the best known algorithm), which motivates the use of parallelism. Parallelism is especially needed for large graphs with millions of vertices and billions of edges. While the the memory requirements for computing be- tweenness are not as demanding, O ( V + E ) (for the best known sequential algorithm), these bound increase for different parallel algorithms. We show that is possible to reduce the memory requirements for computing betweenness centrality from O ( V + E ) to O ( V ) at the expense of doing additional traversals. We show that not only does this not hurt performance it actually improves performance for coarse grain parallelism. Further, we show that using the new approach allows parallel scaling that previously was not possible. One example is that the new approach is able to scale to 40 x86 cores for a graph with 32 M vertices and 2B edges, whereas the previous approach is only able to scale upto 6 cores because of memory requirements. We also do analysis of fine-grain parallel betweenness centrality on both the x86 and the Cray XMT.
The Clay Mathematics Institute has selected seven Millennium Problems to motivate research on important classic questions that have resisted solution over the years. Among them is the central problem in theoretical co...
详细信息
The Clay Mathematics Institute has selected seven Millennium Problems to motivate research on important classic questions that have resisted solution over the years. Among them is the central problem in theoretical computer science: the P versus NP problem, which aims to classify the possible existence of efficient solutions to combinatorial and optimization problems. The main goal is to determine whether there are questions whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. In this context, it is important to determine precisely what facet of a problem makes it NP-complete. We shall discuss classes of problems for which dichotomy results do exist: every problem in the class is classified into polynomial or NP-complete. We shall discuss our contribution through the classification of some long-standing problems in important areas of graph theory: perfect graphs, intersection graphs, and structural characterization of graph classes. More precisely, we have shown that Chvatal's SKEW PARTITIONS polynomial and that Roberts-Spencer's CLIQUE graph is NP-complete. We have also solved the dichotomy for Golumbic-Kaplan-Shamir's SANDWICH problem. We shall describe two examples where we can determine the full dichotomy: the edge-colouring problem for graphs with no cycle with a unique chord and the three nonempty part sandwich problem. Some open problems are discussed: the stubborn problem for list partition, the chromatic index of chordal graphs, and the recognition of split clique graphs. (C) 2010 Elsevier B.V. All rights reserved.
This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space...
详细信息
This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space representation. It is shown that both exact and approximate versions of the problem can be solved in polynomial time in the size of an output graph by using dynamic programming algorithms if the graphs are trees whose maximum degree is bounded by a constant and the lengths of given paths and alphabet size are bounded by constants. On the other hand, it is shown that this problem is strongly NP-hard even for trees of bounded degree if the maximum length of paths is not bounded. The problem of inferring a string from the number of occurrences of fixed size substrings is also studied. (C) 2012 Elsevier B.V. All rights reserved.
In this paper we propose a new approach for the comparison and retrieval of geometric graphs formulated from an alignment perspective. The algorithm presented here is quite general in nature and applies to geometric g...
详细信息
In this paper we propose a new approach for the comparison and retrieval of geometric graphs formulated from an alignment perspective. The algorithm presented here is quite general in nature and applies to geometric graphs of any dimension. The method involves two major steps. Firstly graph alignment is effected making use of an optimisation approach whose target function arises from a diffusion process over the graphs under study. This provides, from the theoretical viewpoint, a link between stochastic processes on graphs and the heat kernel. The second step involves using a probabilistic approach to recover the transformation parameters that map the graph-vertices to one another so as to permit the computation of a similarity measure based on the goodness of fit between the two graphs under study. Here, we view the transformation parameters as random variables and aim at minimising the Kullback-Liebler divergence between the two graphical structures under study. We provide a sensitivity analysis on synthetic data and illustrate the utility of the method for purposes of comparison and retrieval of CAD objects and binary shape categorisation. We also compare our results to those yielded by alternatives elsewhere in the literature. (C) 2012 Elsevier Ltd. All rights reserved.
Given a positive definite matrix M and an integer N-m >= 1, Oja's subspace algorithm will provide convergent estimates of the first N-m eigenvalues of M along with the corresponding eigenvectors. It is a common...
详细信息
Given a positive definite matrix M and an integer N-m >= 1, Oja's subspace algorithm will provide convergent estimates of the first N-m eigenvalues of M along with the corresponding eigenvectors. It is a common approach to principal component analysis. This paper introduces a normalized stochastic-approximation implementation of Oja's subspace algorithm, as well as new applications to the spectral decomposition of a reversible Markov chain. Recall that this means that the stationary distribution satisfies the detailed balance equations (Meyn & Tweedie, 2009). Equivalently, the statistics of the process in steady state do not change when time is reversed. Stability and convergence of Oja's algorithm are established under conditions far milder than that assumed in previous work. Applications to graph clustering, Markov spectral decomposition, and multiplicative ergodic theory are surveyed, along with numerical results. (C) 2012 Elsevier Ltd. All rights reserved.
A binary matrix has the Consecutive Ones Property (C1P) if it is possible to order the columns so that all Is are consecutive in every row. In [McConnell, SODA 2004, pp. 768-777] the notion of incompatibility graph of...
详细信息
A binary matrix has the Consecutive Ones Property (C1P) if it is possible to order the columns so that all Is are consecutive in every row. In [McConnell, SODA 2004, pp. 768-777] the notion of incompatibility graph of a binary matrix was introduced and it was shown that odd cycles of this graph provide a certificate that a matrix does not have the Consecutive Ones Property. A bound of k + 2 was claimed for the smallest odd cycle of a non-C1P matrix with k columns. In this Note we show that this result can be obtained simply and directly via Tucker patterns, and that the correct bound is k + 2 when k is even, but k + 3 when k is odd. (c) 2012 Elsevier B.V. All rights reserved.
How communities form can depend on the geospatial location of people within a social network. Here, we investigated the implementation of the label propagation algorithm (LPA) and LabelRankT community detection algori...
详细信息
ISBN:
(纸本)9781479903016
How communities form can depend on the geospatial location of people within a social network. Here, we investigated the implementation of the label propagation algorithm (LPA) and LabelRankT community detection algorithm in Gephi, a graph visualization tool. We researched extending these community detection algorithms to incorporate the geospatial distance between nodes in a network as a limiting factor for the automatic detection of community formation.
暂无评论