NDLI: Counting stars and other small subgraphs in sublinear time

Please wait, while we are loading the content...

On the optimality of spiral search

An improved competitive algorithm for reordering buffer management

How to meet asynchronously (almost) everywhere

A 1.43-competitive online graph edge coloring algorithm in the random order arrival model

Towards the randomized k-server conjecture: a primal-dual approach

Testing monotone continuous distributions on high-dimensional real cubes

Property testing and parameter testing for permutations

Near-optimal sublinear time algorithms for Ulam distance

Lower bounds for testing triangle-freeness in Boolean functions

Counting stars and other small subgraphs in sublinear time

Cell-probe lower bounds for succinct partial sums

On the cell probe complexity of dynamic membership

Fully-functional succinct trees

Data structures for range minimum queries in multidimensional arrays

Counting inversions, offline orthogonal range counting, and related problems

Differential privacy in new settings

Lower bounds for edit distance and product metrics via Poincaré-type inequalities

Genus and the geometry of the cut graph

Testing planarity of partially embedded graphs

Inapproximability for planar embedding problems

Towards a calculus for non-linear spectral gaps

A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics

PTAS for maximum weight independent set problem with random weights in bounded degree graphs

Belief propagation for min-cost network flow: convergence & correctness

Finding the Jaccard median

The focus of attention problem

Recognizing a totally odd $K_{4}-subdivision,$ parity 2-disjoint rooted paths and a parity cycle through specified elements

Decomposition, approximation, and coloring of odd-minor-free graphs

The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

On brambles, grid-like minors, and parameterized intractability of monadic second-order logic

An (almost) linear time algorithm for odd cycles transversal

An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem

A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing

Region growing for multi-route cuts

Asymmetric traveling salesman path and directed latency problems

Improved approximation algorithms for the minimum latency problem via prize-collecting strolls

Quantum algorithms for highly non-linear Boolean functions

Compact ancestry labeling schemes for XML trees

Generating a d-dimensional linear subspace efficiently

Algorithms for ray class groups and Hilbert class fields

A space-time tradeoff for permutation problems

Algorithmic lower bounds for problems parameterized by clique-width

Bidimensionality and kernels

Solving MAX-r-SAT above a tight lower bound

Inapproximability for VCG-based combinatorial auctions

Price of anarchy for greedy auctions

Incentive compatible budget elicitation in multi-unit auctions

Utilitarian mechanism design for multi-objective optimization

Pricing randomized allocations

Universal ε-approximators for integrals

Optimally reconstructing weighted graphs using queries

Online learning with queries

Coresets and sketches for high dimensional subspace approximation problems

Convergence, stability, and discrete approximation of Laplace spectra

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Fast SDP algorithms for constraint satisfaction problems

Probabilistic analysis of the semidefinite relaxation detector in digital communications

Correlation clustering with noisy input

A polynomial time approximation scheme for k-consensus clustering

Google's auction for TV ads

A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs

Solving the replacement paths problem for planar directed graphs in O(n log n) time

Bounding variance and expectation of longest path lengths in DAGs

Highway dimension, shortest paths, and provably efficient algorithms

Maximum flows and parametric shortest paths in planar graphs

On the equilibria of alternating move games

Monotonicity in bargaining networks

Sharp dichotomies for regret minimization in metric spaces

Solving simple stochastic tail games

One-counter Markov decision processes

On nonlinear forbidden 0-1 matrices: a refutation of a Füredi-Hajnal conjecture

An improved construction of progression-free sets

Geometric optimization and sums of algebraic functions

Approximating the crossing number of graphs embeddable in any orientable surface

How far can you reach?

A model of computation for MapReduce

Synchrony and asynchrony in neural networks

Distributed agreement with optimal communication complexity

How good is the Chord algorithm?

Deterministic algorithms for the Lovász Local Lemma

A deterministic truthful PTAS for scheduling related machines

A Fourier space algorithm for solving quadratic assignment problems

EDF-schedulability of synchronous periodic task systems is coNP-hard

Reconstructing approximate phylogenetic trees from quartet samples

Shape replication through self-assembly and RNase enzymes

On the possibility of faster SAT algorithms

Paired approximation problems and incompatible inapproximabilities

Correlation robust stochastic optimization

Approximability of robust network design

Differentially private combinatorial optimization

Efficiently decodable non-adaptive group testing

1-pass relative-error $L_{p}-sampling$ with applications

On the exact space complexity of sketching and streaming small norms

A locality-sensitive hash for real vectors

Lower bounds for sparse recovery

Flow-cut gaps for integer and fractional multiflows

A max-flow/min-cut algorithm for a class of wireless networks

Testing additive integrality gaps

Classified stable matching

Basis reduction and the complexity of branch-and-bound

Randomized Shellsort: a simple oblivious sorting algorithm

Data-specific analysis of string sorting

Fast distance multiplication of unit-Monge matrices

Regular expression matching with multi-strings and intervals

Road network reconstruction for organizing paths

The power of convex relaxation: the surprising stories of matrix completion and compressed sensing

An online scalable algorithm for average flow time in broadcast scheduling

Resource minimization for fire containment

Algorithms and complexity for periodic real-time scheduling

Energy efficient scheduling via partial shutdown

SRPT is 1.86-competitive for completion time scheduling

The rank of diluted random graphs

The scaling window for a random graph with a given degree sequence

Efficient broadcast on random geometric graphs

Speeding up random walks with neighborhood exploration

Vertices of degree k in random maps

Cache-oblivious dynamic dictionaries with update/query tradeoffs

Applications of forbidden 0-1 matrices to search tree and path compression-based data structures

Faster exponential time algorithms for the shortest vector problem

Streaming algorithms for extent problems in high dimensions

Deletion without rebalancing in balanced binary trees

On linear and semidefinite programming relaxations for hypergraph matching

Partition constrained covering of a symmetric crossing supermodular function by a graph

Tree embeddings for two-edge-connected network design

A constant factor approximation algorithm for generalized min-sum set cover

Self-improving algorithms for convex hulls

The forest hiding problem: an illumination problem for maximal disk packings

Terrain guarding is NP-hard

Hardness results for homology localization

Orthogonal ham-sandwich theorem in $R^{3}$

The (1 + β)-choice process and weighted balls-into-bins

Quasirandom load balancing

Thin partitions: isoperimetric inequalities and a sampling algorithm for star shaped bodies

Phase transition for the mixing time of the Glauber dynamics for coloring regular trees

Rumour spreading and graph conductance

Counting stars and other small subgraphs in sublinear time

Content Provider	ACM Digital Library
Author	Gonen, Mira Ron, Dana Shavitt, Yuval
Abstract	Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph G. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter 0 < ε < 1 and query access to a graph G, outputs an estimate $vC_{s}$ such that with high constant probability, $(1-ε)v_{s}(G)$ ≤ $v_{s}$ ≤ (1 + $ε)v_{s}(G),$ where $v_{s}(G)$ denotes the number of stars of size s + 1 in the graph. The expected query complexity and running time of the algorithm are [EQUATION] poly (log n, 1/ε). We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in n and the dependence on ε. Our work extends the work of Feige (SIAM Journal on Computing, 2006) and Goldreich and Ron (Random Structures and Algorithms, 2008) on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to obtain an estimate on the variance of the degrees in the graph and corresponding higher moments. In addition, we give some (negative) results on approximating the number of triangles and on approximating the number of length-3-paths in sublinear time.
Starting Page	99
Ending Page	116
Page Count	18
File Format	PDF
ISBN	9780898716986
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-01-17
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in