Consistency thresholds for the planted bisection model. (English) Zbl 1321.05242
Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 69-75 (2015).
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
graph clustering; minimum bisection; planted partition model; random graph; stochastic block modelSoftware:
GraphsReferences:
| [1] | E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. Arxiv 1405.3267. |
| [2] | Arash A. Amini, Aiyou Chen, Peter J. Bickel, and Elizaveta Levina. Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, 41(4):2097-2122, 08 2013. · Zbl 1277.62166 |
| [3] | P.J. Bickel and A. Chen. A nonparametric view of network models and Newman-Girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):21068-21073, 2009. · Zbl 1359.62411 |
| [4] | R.B. Boppana. Eigenvalues and graph bisection: An average-case analysis. In 28th Annual Symposium on Foundations of Computer Science, pages 280-285. IEEE, 1987. 10.1109/SFCS.1987.22 |
| [5] | T.N. Bui, S. Chaudhuri, F.T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171-191, 1987. 10.1007/BF02579448 |
| [6] | T. Carson and R. Impagliazzo. Hill-climbing finds random planted bisections. In Twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 903-909. Society for Industrial and Applied Mathematics, 2001. · Zbl 1014.05059 |
| [7] | A. Coja-Oghlan. Graph partitioning via adaptive spectral techniques. Combinatorics, Probability and Computing, 19(02):227-284, 2010. 10.1017/S0963548309990514 · Zbl 1209.05178 |
| [8] | A. Condon and R.M. Karp. Algorithms for graph partitioning on the planted partition model. Random Structures and Algorithms, 18(2):116-140, 2001. 10.1002/1098-2418(200103)18:2 · Zbl 0972.68129 |
| [9] | M.E. Dyer and A.M. Frieze. The solution of some random NP-hard problems in polynomial expected time. Journal of Algorithms, 10(4):451-489, 1989. 10.1016/0196-6774(89)90001-1 · Zbl 0689.68049 |
| [10] | Paul Erdos and Alfréd Rényi. On the strength of connectedness of a random graph. Acta Mathematica Hungarica, 12(1):261-267, 1961. · Zbl 0103.16302 |
| [11] | P.W. Holland, K.B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109 – 137, 1983. |
| [12] | M. Jerrum and G.B. Sorkin. The Metropolis algorithm for graph bisection. Discrete Applied Mathematics, 82(1-3):155-175, 1998. 10.1016/S0166-218X(97)00133-9 · Zbl 0932.60079 |
| [13] | R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. · Zbl 1467.68065 |
| [14] | János Komlós and Endre Szemerédi. Limit distribution for the existence of hamiltonian cycles in a random graph. Discrete Mathematics, 43(1):55-63, 1983. 10.1016/0012-365X(83)90021-3 · Zbl 0521.05055 |
| [15] | Amit Kumar and Ravindran Kannan. Clustering with spectral norm and the k-means algorithm. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 299-308. IEEE, 2010. 10.1109/FOCS.2010.35 |
| [16] | Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Approximation algorithms for semi-random partitioning problems. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 367-384. ACM, 2012. 10.1145/2213977.2214013 · Zbl 1286.68504 |
| [17] | Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Constant factor approximation for balanced cut in the pie model. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 41-49. ACM, 2014. 10.1145/2591796.2591841 · Zbl 1315.05114 |
| [18] | Laurent Massoulié. Community detection thresholds and the weak ramanujan property. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 694-703. ACM, 2014. 10.1145/2591796.2591857 · Zbl 1315.68210 |
| [19] | F. McSherry. Spectral partitioning of random graphs. In 42nd IEEE Symposium on Foundations of Computer Science, pages 529-537. IEEE, 2001. |
| [20] | E. Mossel, J. Neeman, and A. Sly. Belief propagation, robust reconstruction, and optimal recovery of block models (extended abstract). JMLR Workshop and Conference Proceedings (COLT proceedings), 35:1-35, 2014. Winner of best paper award at COLT 2014. |
| [21] | E. Mossel, J. Neeman, and A. Sly. Stochastic block models and reconstruction. Probability Theory and Related Fields, 2014. (to appear). |
| [22] | Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. (submitted to Combinatorica), 2014. |
| [23] | Raj Rao Nadakuditi and Mark EJ Newman. Graph spectra and the detectability of community structure in networks. Physical Review Letters, 108(18):188701, 2012. |
| [24] | Yoav Seginer. The expected norm of random matrices. Combinatorics, Probability and Computing, 9:149-166, 3 2000. 10.1017/S096354830000420X · Zbl 0969.15009 |
| [25] | Van H. Vu. Spectral norm of random matrices. Combinatorica, 27(6):721-736, 2007. 10.1007/s00493-007-2190-z · Zbl 1164.05066 |
| [26] | Se-Young Yun and Alexandre Proutiere. Community detection via random and adaptive sampling. arXiv preprint arXiv:1402.3072, 2014. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
