We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subset of vertices. This can be regarded as a model for the problem of finding a tightly knitted community in a social network, or a cluster in a relational dataset. In this paper we present two sets of contributions: (i) We use the cavity method from spin glass theory to derive an exact phase diagram for the reconstruction problem. In particular, as the difference in edge probability increases, the problem undergoes two phase transitions, a static phase transition and a dynamic one. (ii) We establish rigorous bounds on the dynamic phase transition and prove that, above a certain threshold, a local algorithm (belief propagation) correctly identify most of the hidden set. Below the same threshold no local algorithm can achieve this goal. However, in this regime the subset can be identified by exhaustive search. For small hidden sets and large average degree, the phase transition for local algorithms takes an intriguingly simple form. Local algorithms succeed with high probability for ( _ in - _ out > _ out e ) and fail for ( _ in - _ out < _ out e ) (with ( _ in ), ( _ out ) the average degrees inside and outside the community). We argue that spectral algorithms are also ineffective in the latter regime. It is an open problem whether any polynomial time algorithms might succeed for ( _ in - _ out < _ out e ).
In the sparse graph setting considered here, the approach fails because the operator norm @math is unbounded as @math . Concretely, the sparse graph @math has large eigenvalues of order @math localized on the vertices of largest degree. This point was already discussed in several related problems @cite_5 @cite_39 @cite_36 @cite_17 @cite_24 . Several techniques have been proposed to address this problem, the crudest one being to remove high-degree vertices.
@cite_36 @cite_39 @cite_24 @cite_5 @cite_17
2144730813 2133361319 1914749871 2021145763 2024514015
We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ1 ≥ … ≥ λn be the eigenvalues of an n-vertex graph, and let λ = max[λ2,|λn|]. Let c be a large enough constant. For graphs of average degree d = c log n it is well known that λ1 ≥ d, and we show that @math . For d = c it is no longer true that @math , but we show that by removing a small number of vertices of highest degree in G, one gets a graph G′ for which @math . Our proofs are based on the techniques of Friedman Kahn and Szemeredi from STOC 1989, who proved similar results for regular graphs. Our results are useful for extending the analysis of certain heuristics to sparser instances of NP-hard problems. We illustrate this by removing some unnecessary logarithmic factors in the density of k-SAT formulas that are refuted by the algorithm of Goerdt and Krivelevich from STACS 2001. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 Consider an Erdos---Renyi random graph in which each edge is present independently with probability @math 1 2, except for a subset @math CN of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The algorithm of (ANALCO. SIAM, pp 67---75, 2011) provably identifies the clique @math CN in linear time, provided @math |CN|?1.261N. Spectral methods can be shown to fail on cliques smaller than @math N. In this paper we describe a nearly linear-time algorithm that succeeds with high probability for @math |CN|?(1+?)N e for any @math ?>0. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on @math N vertices). For large-girth regular graphs of degree @math (Δ+1) we prove that so-called local algorithms succeed if @math |CN|?(1+?)N eΔ and fail if @math |CN|≤(1-?)N eΔ. Distributed voting is a fundamental topic in distributed computing. In the standard model of pull voting, at each step every vertex chooses a neighbour uniformly at random and adopts its opinion. The voting is completed when all vertices hold the same opinion. In the simplest case, each vertex initially holds one of two different opinions. This partitions the vertices into arbitrary sets A and B. For many graphs, including regular graphs and irrespective of their expansion properties, if both A and B are sufficiently large sets, then pull voting requires @math expected steps, where n is the number of vertices of the graph. In this paper we consider a related class of voting processes based on sampling two opinions. In the simplest case, every vertex v chooses two random neighbours at each step. If both these neighbours have the same opinion, then v adopts this opinion. Otherwise, v keeps its own opinion. Let G be a connected graph with n vertices and m edges. Let P be the transition matrix of a simple random walk on G with second largest eigenvalue @math . We show that if the initial imbalance in degree between the two opinions satisfies @math , then with high probability voting completes in @math steps, and the opinion with the larger initial degree wins. The condition that @math , or only a bound on the conductance of the graph is known, the sampling process can be modified so that voting still provably completes in @math steps with high probability. The modification uses two sampling based on probing to a fixed depth @math from any vertex. In its most general form our voting process allows vertices to bias their sampling of opinions among their neighbours to achieve a desired outcome. This is done by allocating weights to edges.