Document

**Published in:** LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting 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 computationally 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.
In addition, our methods give the first computational lower bounds for testing between two different "planted" distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. "null" distribution.

Cynthia Rush, Fiona Skerman, Alexander S. Wein, and Dana Yang. Is It Easier to Count Communities Than Find Them?. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 94:1-94:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rush_et_al:LIPIcs.ITCS.2023.94, author = {Rush, Cynthia and Skerman, Fiona and Wein, Alexander S. and Yang, Dana}, title = {{Is It Easier to Count Communities Than Find Them?}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {94:1--94:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.94}, URN = {urn:nbn:de:0030-drops-175970}, doi = {10.4230/LIPIcs.ITCS.2023.94}, annote = {Keywords: Community detection, Hypothesis testing, Low-degree polynomials} }

Document

**Published in:** LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be NP-complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph G. We show that the problem belongs to FPT when parameterised by the size of a minimum vertex cover for G, and is solvable in polynomial time whenever the treewidth or max leaf number of G is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.

Kitty Meeks and Fiona Skerman. The Parameterised Complexity of Computing the Maximum Modularity of a Graph. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{meeks_et_al:LIPIcs.IPEC.2018.9, author = {Meeks, Kitty and Skerman, Fiona}, title = {{The Parameterised Complexity of Computing the Maximum Modularity of a Graph}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.9}, URN = {urn:nbn:de:0030-drops-102103}, doi = {10.4230/LIPIcs.IPEC.2018.9}, annote = {Keywords: modularity, community detection, integer quadratic programming, vertex cover, pathwidth} }

Document

**Published in:** LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

We investigate the number of permutations that occur in random node labellings of trees. This is a generalisation of the number of subpermutations occuring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees [Cai et al., 2017]. We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye [Devroye, 1998]. Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes.
For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree with high probability the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.

Michael Albert, Cecilia Holmgren, Tony Johansson, and Fiona Skerman. Permutations in Binary Trees and Split Trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 9:1-9:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{albert_et_al:LIPIcs.AofA.2018.9, author = {Albert, Michael and Holmgren, Cecilia and Johansson, Tony and Skerman, Fiona}, title = {{Permutations in Binary Trees and Split Trees}}, booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)}, pages = {9:1--9:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-078-1}, ISSN = {1868-8969}, year = {2018}, volume = {110}, editor = {Fill, James Allen and Ward, Mark Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.9}, URN = {urn:nbn:de:0030-drops-89025}, doi = {10.4230/LIPIcs.AofA.2018.9}, annote = {Keywords: random trees, split trees, permutations, inversions, cumulant} }

Document

**Published in:** LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees [Devroye, 1999], we show that X_n converges to the unique solution of a distributional equation. Finally, when T_n's are conditional Galton-Watson trees, we show that X_n converges to a random variable defined in terms of Brownian excursions. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].

Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson, and Fiona Skerman. Inversions in Split Trees and Conditional Galton-Watson Trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 15:1-15:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.AofA.2018.15, author = {Cai, Xing Shi and Holmgren, Cecilia and Janson, Svante and Johansson, Tony and Skerman, Fiona}, title = {{Inversions in Split Trees and Conditional Galton-Watson Trees}}, booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)}, pages = {15:1--15:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-078-1}, ISSN = {1868-8969}, year = {2018}, volume = {110}, editor = {Fill, James Allen and Ward, Mark Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.15}, URN = {urn:nbn:de:0030-drops-89085}, doi = {10.4230/LIPIcs.AofA.2018.15}, annote = {Keywords: inversions, random trees, split trees, Galton-Watson trees, permutation, cumulant} }

Document

**Published in:** LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

For a given graph G, modularity gives a score to each vertex partition, with higher values taken to indicate that the partition better captures community structure in G. The modularity q^*(G) (where 0 <= q^*(G)<= 1) of the graph G is defined to be the maximum over all vertex partitions of the modularity value. Given the prominence of modularity in community detection, it is an important graph parameter to understand mathematically.
For the Erdös-Rényi random graph G_{n,p} with n vertices and edge-probability p, the likely modularity has three distinct phases. For np <= 1+o(1) the modularity is 1+o(1) with high probability (whp), and for np --> infty the modularity is o(1) whp. Between these regions the modularity is non-trivial: for constants 1 < c_0 <= c_1 there exists delta>0 such that when c_0 <= np <= c_1 we have delta<q^*(G)<1-delta whp. For this critical region, we show that whp q^*(G_{n,p}) has order (np)^{-1/2}, in accord with a conjecture by Reichardt and Bornholdt in 2006 (and disproving another conjecture from the physics literature).

Colin McDiarmid and Fiona Skerman. Modularity of Erdös-Rényi Random Graphs. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 31:1-31:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mcdiarmid_et_al:LIPIcs.AofA.2018.31, author = {McDiarmid, Colin and Skerman, Fiona}, title = {{Modularity of Erd\"{o}s-R\'{e}nyi Random Graphs}}, booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)}, pages = {31:1--31:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-078-1}, ISSN = {1868-8969}, year = {2018}, volume = {110}, editor = {Fill, James Allen and Ward, Mark Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.31}, URN = {urn:nbn:de:0030-drops-89242}, doi = {10.4230/LIPIcs.AofA.2018.31}, annote = {Keywords: Community detection, Newman-Girvan Modularity, random graphs} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail