×

Detecting communities is hard (and counting them is even harder). (English) Zbl 1402.68106

Papadimitriou, Christos H. (ed.), 8th innovations in theoretical computer science conference, ITCS 2017, Berkeley, CA, USA, January 9–11, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-029-3). LIPIcs – Leibniz International Proceedings in Informatics 67, Article 42, 13 p. (2017).
Summary: We consider the algorithmic problem of community detection in networks. Given an undirected friendship graph \(G=(V,E)\), a subset \(S\subseteq V\) is an \((\alpha,\beta)\)-community if:
\(\bullet\) Every member of the community is friends with an \(\alpha\)-fraction of the community;
\(\bullet\) Every non-member is friends with at most a \(\beta\)-fraction of the community.
S. Arora et al. [“Finding overlapping communities in social networks: toward a rigorous approach”, in: Proceedings of the 13th ACM conference on electronic commerce, EC ’12. New York, NY: Association for Computing Machinery (ACM). 37–54 (2012; doi:10.1145/2229012.2229020)] gave a quasi-polynomial time algorithm for enumerating all the \((\alpha,\beta)\)-communities for any constants \(\alpha>\beta\).
Here, we prove that, assuming the Exponential Time Hypothesis (ETH), quasi-polynomial time is in fact necessary – and even for a much weaker approximation desideratum. Namely, distinguishing between:
\(\bullet\) \(G\) contains an \((1,o(1))\)-community; and
\(\bullet\) \(G\) does not contain a \((\beta+o(1),\beta)\)-community for any \(\beta\in[0,1]\).
We also prove that counting the number of \((1,o(1))\)-communities requires quasi-polynomial time assuming the weaker #ETH.
For the entire collection see [Zbl 1379.68010].

MSC:

68Q25 Analysis of algorithms and problem complexity
05C82 Small world graphs, complex networks (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[2] Scott Aaronson, Russell Impagliazzo, and Dana Moshkovitz. AM with multiple merlins.In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 44-55. IEEE,2014.
[3] Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithmfor the maximal independent set problem. J. Algorithms, 7(4):567-583, 1986. doi:10.1016/0196-6774(86)90019-2.
[4] Sanjeev Arora, Rong Ge, Sushant Sachdeva, and Grant Schoenebeck. Finding overlappingcommunities in social networks: toward a rigorous approach.In ACM Conference onElectronic Commerce, EC ’12, Valencia, Spain, June 4-8, 2012, pages 37-54, 2012. doi:10.1145/2229012.2229020.
[5] Yakov Babichenko, Christos H. Papadimitriou, and Aviad Rubinstein. Can almost every-body be almost happy?In Proceedings of the 2016 ACM Conference on Innovations inTheoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 1-9,2016. doi:10.1145/2840728.2840731. · Zbl 1335.91021
[6] Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer T. Chayes, and Shang-Hua Teng.Finding endogenously formed communities.In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans,Louisiana, USA, January 6-8, 2013, pages 767-783, 2013. doi:10.1137/1.9781611973105.55. · Zbl 1422.68203
[7] Afonso S. Bandeira, Nicolas Boumal, and Vladislav Voroninski. On the low-rank approachfor semidefinite programs arising in synchronization and community detection. In Pro-ceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June23-26, 2016, pages 361-382, 2016. URL: http://jmlr.org/proceedings/papers/v49/bandeira16.html. · Zbl 1445.90074
[8] Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli. Information-theoreticthresholds for community detection in sparse networks. In Proceedings of the 29th Confer-
[9] Siddharth Barman. Approximating nash equilibria and dense bipartite subgraphs via anapproximate version of caratheodory’s theorem. In Proceedings of the Forty-Seventh AnnualACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 361-369, 2015. doi:10.1145/2746539.2746566. · Zbl 1322.91006
[10] Shai Ben-David and Margareta Ackerman.Measures of clustering quality:Aworking set of axioms for clustering.In Advances in Neural Information Pro-cessing Systems 21, Proceedings of the Twenty-Second Annual Conference on NeuralInformationProcessingSystems,Vancouver,BritishColumbia,Canada,Decem-ber8-11,2008,pages121-128,2008.URL:http://papers.nips.cc/paper/3491-measures-of-clustering-quality-a-working-set-of-axioms-for-clustering.
[11] Umang Bhaskar, Yu Cheng, Young Kun Ko, and Chaitanya Swamy. Hardness results forsignaling in bayesian zero-sum and network routing games. In Proceedings of the 2016ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands,July 24-28, 2016, pages 479-496, 2016. doi:10.1145/2940716.2940753.
[12] Christian Borgs, Jennifer T. Chayes, Adrian Marple, and Shang-Hua Teng. An axiomaticapproach to community detection. In Proceedings of the 2016 ACM Conference on Innova-tions in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages135-146, 2016. doi:10.1145/2840728.2840748. · Zbl 1334.91061
[13] Mark Braverman, Young Kun-Ko, Aviad Rubinstein, and Omri Weinstein. ETH hardnessfor densest-\(k\)-subgraph with perfect completeness. In SODA, 2017. To appear. · Zbl 1409.68125
[14] Mark Braverman, Young Kun-Ko, and Omri Weinstein. Approximating the best nashequilibrium in no(log n)-time breaks the exponential time hypothesis.In Proceedingsof the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA2015, San Diego, CA, USA, January 4-6, 2015, pages 970-982, 2015. doi:10.1137/1.9781611973730.66. · Zbl 1372.68112
[15] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiab-ility of small depth circuits. In Parameterized and Exact Computation, 4th InternationalWorkshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised SelectedPapers, pages 75-85, 2009. doi:10.1007/978-3-642-11269-0_6. · Zbl 1273.68159
[16] Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi,and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypo-thesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conferenceon Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16,2016, pages 261-270, 2016. doi:10.1145/2840728.2840746. · Zbl 1334.68079
[17] Yuxin Chen, Govinda M. Kamath, Changho Suh, and David Tse. Community recoveryin graphs with locality. In Proceedings of the 33nd International Conference on MachineLearning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pages 689-698, 2016.URL: http://jmlr.org/proceedings/papers/v48/chena16.html.
[18] Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, andShang-Hua Teng. Mixture selection, mechanism design, and signaling. In IEEE 56th AnnualSymposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20October, 2015, pages 1426-1445, 2015. doi:10.1109/FOCS.2015.91.
[19] Argyrios Deligkas, John Fearnley, and Rahul Savani. Inapproximability results for approx-imate nash equilibria. CoRR, abs/1608.03574, 2016. URL: http://arxiv.org/abs/1608.03574. · Zbl 1404.91004
[20] Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactiveproofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43(2):268-292, 1996. · Zbl 0882.68129
[21] Laura Florescu and Will Perkins. Spectral thresholds in the bipartite stochastic block model.In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA,June 23-26, 2016, pages 943-959, 2016. URL: http://jmlr.org/proceedings/papers/v49/florescu16.html.
[22] Santo Fortunato. Community detection in graphs. Physics Reports, 486:75-174, 2010.
[23] Bruce E. Hajek, Yihong Wu, and Jiaming Xu. Semidefinite programs for exact recovery ofa hidden community. In Proceedings of the 29th Conference on Learning Theory, COLT2016, New York, USA, June 23-26, 2016, pages 1051-1095, 2016. URL: http://jmlr.org/proceedings/papers/v49/hajek16.html.
[24] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic block-models: First steps. Social Networks, 5:109-137, 1983.
[25] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst.Sci., 62(2):367-375, 2001. · Zbl 0990.68079
[26] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have stronglyexponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. doi:10.1006/jcss.2001.1774. · Zbl 1006.68052
[27] Jon M. Kleinberg. An impossibility theorem for clustering. In Advances in Neural In-formation Processing Systems 15 [Neural Information Processing Systems, NIPS 2002,December 9-14, 2002, Vancouver, British Columbia, Canada], pages 446-453, 2002. URL:http://papers.nips.cc/paper/2340-an-impossibility-theorem-for-clustering.
[28] Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games usingsimple strategies. In EC, pages 36-41, 2003.
[29] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Learning com-munities in the presence of errors. In Proceedings of the 29th Conference on LearningTheory, COLT 2016, New York, USA, June 23-26, 2016, pages 1258-1291, 2016. URL:http://jmlr.org/proceedings/papers/v49/makarychev16.html. · Zbl 1315.05114
[30] Pasin Manurangsi. Almost-Polynomial Ratio ETH-Hardness of Approximating Densestk-Subgraph with Perfect Completeness. CoRR, abs/1611.05991, 2016. · Zbl 1370.68110
[31] Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert Endre Tarjan. Clusteringsocial networks. In Algorithms and Models for the Web-Graph, 5th International Workshop,WAW 2007, San Diego, CA, USA, December 11-12, 2007, Proceedings, pages 56-67, 2007.doi:10.1007/978-3-540-77004-6_5. · Zbl 1136.91590
[32] Ankur Moitra, William Perry, and Alexander S. Wein. How robust are reconstructionthresholds for community detection?In Proceedings of the 48th Annual ACM SIGACTSymposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21,2016, pages 828-841, 2016. doi:10.1145/2897518.2897573. · Zbl 1381.62190
[33] Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. J. ACM, 57(5),2010. doi:10.1145/1754399.1754402. · Zbl 1327.68110
[34] Elchanan Mossel and Jiaming Xu. Density evolution in the degree-correlated stochasticblock model. In Proceedings of the 29th Conference on Learning Theory, COLT 2016,New York, USA, June 23-26, 2016, pages 1319-1356, 2016.URL: http://jmlr.org/proceedings/papers/v49/mossel16.html.
[35] Aviad Rubinstein.Eth-hardness for signaling in symmetric zero-sum games.CoRR,abs/1510.04991, 2015. URL: http://arxiv.org/abs/1510.04991.
[36] Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equi-libria. In To appear in FOCS, 2016.
[37] Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan.Chernoff-hoeffding boundsfor applications with limited independence. SIAM J. Discrete Math., 8(2):223-250, 1995.doi:10.1137/S089548019223872X. · Zbl 0819.60032
[38] Nicolas Tremblay, Gilles Puy, Rémi Gribonval, and Pierre Vandergheynst. Compressivespectral clustering. In Proceedings of the 33nd International Conference on Machine Learn-ing, ICML 2016, New York City, NY, USA, June 19-24, 2016, pages 1002-1011, 2016. URL:http://jmlr.org/proceedings/papers/v48/tremblay16.html.
[39] Twan van Laarhoven and Elena Marchiori. Axioms for graph clustering quality functions.Journal of Machine Learning Research, 15(1):193-215, 2014. URL: http://dl.acm.org/citation.cfm?id=2627441. · Zbl 1318.62222
[40] :13
[41] :12
[42] :11ence on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, pages 383-416,2016. URL: http://jmlr.org/proceedings/papers/v49/banks16.html.
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.