Counting the frequencies of 3-, 4-, and 5-node undirected motifs (also know as graphlets) is widely used for understanding complex networks such as social and biology networks. However, it is a great challenge to compute these metrics for a large graph due to the intensive computation. Despite recent efforts to count triangles (i.e., 3-node undirected motif counting), little attention has been given to developing scalable tools that can be used to characterize 4- and 5-node motifs. In this paper, we develop computational efficient methods to sample and count 4- and 5- node undirected motifs. Our methods provide unbiased estimators of motif frequencies, and we derive simple and exact formulas for the variances of the estimators. Moreover, our methods are designed to fit vertex centric programming models, so they can be easily applied to current graph computing systems such as Pregel and GraphLab. We conduct experiments on a variety of real-word datasets, and experimental results show that our methods are several orders of magnitude faster than the state-of-the-art methods under the same estimation errors.
In this paper, we study the problem of computing 4- and 5-node motifs' frequencies for , which is much different from the problem of computing the number of subgraph patterns appearing in studied in @cite_2 . Recently, a lot of efforts has been devoted to design sampling methods for computing a large graph's motif concentrations @cite_13 @cite_0 @cite_8 @cite_29 @cite_1 @cite_19 . However, these methods fail to compute motif frequencies, which is more fundamental than motif concentrations. @cite_22 propose the color-coding method to reduce the computational cost of counting subgraphs. Color coding reduces the computations by coloring nodes randomly and enumerating only colorful CISes (i.e., CISes that are consisted of nodes with distinct colors), but @cite_16 reaveals that the color-coding method is not scalable and is hindered by the sheer number of colorful CISes. @cite_28 @cite_5 @cite_21 @cite_3 develop sampling methods to estimate the number of triangles of static and dynamic graphs. @cite_26 develop sampling methods to estimate 4-node undirected motifs' frequencies. However their methods are edge centric methods, which cannot be easily applied to current vertex centric graph computing systems such as GraphLab @cite_10 and GraphChi @cite_4 . Moreover, their methods fail to sample and count 5-node motifs.
@cite_26 @cite_4 @cite_22 @cite_8 @cite_28 @cite_10 @cite_29 @cite_21 @cite_1 @cite_3 @cite_0 @cite_19 @cite_2 @cite_5 @cite_16 @cite_13
2610844084 2015854350 2179569280 2949484202
We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovasz show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. We use the framework of graph motif parameters to obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G. More precisely, for graphs H on k edges, we show how to count subgraph copies of H in time kO(k)· n0.174k + o(k) by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k + c) time for k-edge matchings or O(n0.46k + c) time for k-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating f e C on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G, where H is from a fixed class of graphs, we want to count color-preserving H-copies in G. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions. We present a new shared-memory parallel algorithm and implementation called FASCIA for the problems of approximate sub graph counting and sub graph enumeration. The problem of sub graph counting refers to determining the frequency of occurrence of a given sub graph (or template) within a large network. This is a key graph analytic with applications in various domains. In bioinformatics, sub graph counting is used to detect and characterize local structure (motifs) in protein interaction networks. Exhaustive enumeration and exact counting is extremely compute-intensive, with running time growing exponentially with the number of vertices in the template. In this work, we apply the color coding technique to determine approximate counts of non-induced occurrences of the sub graph in the original network. Color coding gives a fixed-parameter algorithm for this problem, using a dynamic programming-based counting approach. Our new contributions are a multilevel shared-memory parallelization of the counting scheme and several optimizations to reduce the memory footprint. We show that approximate counts can be obtained for templates with up to 12 vertices, on networks with up to millions of vertices and edges. Prior work on this problem has only considered out-of-core parallelization on distributed platforms. With our new counting scheme, data layout optimizations, and multicore parallelism, we demonstrate a significant speedup over the current state-of-the-art for sub graph counting. In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph (G,w) where the weight function w on the edges of G represents the noise (interference) between the two end-vertices. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted t-improper k-colouring of (G,w) is a k-colouring of the nodes of G (assignment of k frequencies) such that the interference at each node does not exceed the threshold t. We consider here the Weighted Improper Colouring problem which consists in determining the weighted t-improper chromatic number defined as the minimum integer k such that (G,w) admits a weighted t-improper k-colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number k of colours, we want to determine the minimum real t such that (G,w) admits a weighted t-improper k-colouring. We first present general upper bounds for both problems; in particular we show a generalisation of Lovasz@?s Theorem for the weighted t-improper chromatic number. Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1 2 for the nodes at distance two. We derive the weighted t-improper chromatic number for all values of t. The problem of counting occurrences of query graphs in a large data graph, known as subgraph counting, is fundamental to several domains such as genomics and social network analysis. Many important special cases (e.g. triangle counting) have received significant attention. Color coding is a very general and powerful algorithmic technique for subgraph counting. Color coding has been shown to be effective in several applications, but scalable implementations are only known for the special case of tree queries (i.e. queries of treewidth one). In this paper we present the first efficient distributed implementation for color coding that goes beyond tree queries: our algorithm applies to any query graph of treewidth @math . Since tree queries can be solved in time linear in the size of the data graph, our contribution is the first step into the realm of colour coding for queries that require superlinear running time in the worst case. This superlinear complexity leads to significant load balancing problems on graphs with heavy tailed degree distributions. Our algorithm structures the computation to work around high degree nodes in the data graph, and achieves very good runtime and scalability on a diverse collection of data and query graph pairs as a result. We also provide theoretical analysis of our algorithmic techniques, showing asymptotic improvements in runtime on random graphs with power law degree distributions, a popular model for real world graphs.