ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Is it easier to count communities than find them? A pair (G, H) of correlated Erdős-Rényi random graphs on n vertices is generated by drawing independently for each of the n(n − 1)/2 couples on vertices a pair of correlated Bernouilli random variables of mean \lambda/n and of correlation parameter s, and including the corresponding edge in G and H according to these random variables. Consider now G′ obtained from H through a random permutation of its vertices; the graph alignment problem is to infer the permutation from the observation of the pair (G, G′ ). Depending on the values of the mean degree \lambda and the correlation s this task might be, in the large size limit where n diverges, either information-theoretically impossible, possible with a polynomial time algorithm, or possible but requiring a priori an exponential time. This talk will summarizes a series of recent results on the boundaries of these phases, emphasizing in particular the role played by Otter’s constant (related to the growth rate of the cardinality of unlabelled trees) as a correlation threshold. Random graph models with community structure have been extensively studied. For both the problems of detecting and recovering community structure, an inter- esting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be compu- tationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show in the low-degree polynomial framework that testing between two options is as hard as finding the communities. Our methods give the first com- putational lower bounds for testing between two different “planted” distributions,

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.