{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:22:17Z","timestamp":1763468537420,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T00:00:00Z","timestamp":1573171200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T00:00:00Z","timestamp":1573171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000332","name":"Royal Society of Edinburgh","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000332","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007459","name":"Ragnar S\u00f6derbergs stiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>The <jats:italic>maximum modularity<\/jats:italic> 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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mi>NP<\/mml:mi>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>-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\u00a0<jats:italic>G<\/jats:italic>. We show that the problem belongs to <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {FPT}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mi>FPT<\/mml:mi>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> when parameterised by the size of a minimum vertex cover for\u00a0<jats:italic>G<\/jats:italic>, and is solvable in polynomial time whenever the treewidth or max leaf number of\u00a0<jats:italic>G<\/jats:italic> 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.<\/jats:p>","DOI":"10.1007\/s00453-019-00649-7","type":"journal-article","created":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T15:35:55Z","timestamp":1573227355000},"page":"2174-2199","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The Parameterised Complexity of Computing the Maximum Modularity of a Graph"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5299-3073","authenticated-orcid":false,"given":"Kitty","family":"Meeks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fiona","family":"Skerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,8]]},"reference":[{"issue":"6","key":"649_CR1","doi-asserted-by":"publisher","first-page":"066118","DOI":"10.1103\/PhysRevE.85.066118","volume":"85","author":"JP Bagrow","year":"2012","unstructured":"Bagrow, J.P.: Communities and bottlenecks: trees and treelike networks have high modularity. Phys. Rev. E 85(6), 066118 (2012)","journal-title":"Phys. Rev. E"},{"issue":"10","key":"649_CR2","doi-asserted-by":"publisher","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech Theory Exp. 2008(10), P10008 (2008)","journal-title":"J. Stat. Mech Theory Exp."},{"key":"649_CR3","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC \u201993, pp. 226\u2013234. ACM, New York, NY, USA (1993). \nhttps:\/\/doi.org\/10.1145\/167088.167161","DOI":"10.1145\/167088.167161"},{"issue":"2","key":"649_CR4","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","volume":"20","author":"U Brandes","year":"2008","unstructured":"Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., Wagner, D.: On modularity clustering. IEEE Trans. Knowl. Data Eng. 20(2), 172\u2013188 (2008). \nhttps:\/\/doi.org\/10.1109\/TKDE.2007.190689","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"649_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)"},{"issue":"1","key":"649_CR6","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.jcss.2012.04.003","volume":"79","author":"B DasGupta","year":"2013","unstructured":"DasGupta, B., Desai, D.: On the complexity of newman\u2019s community finding approach for biological and social networks. J. Comput. Syst. Sci. 79(1), 50\u201367 (2013). \nhttps:\/\/doi.org\/10.1016\/j.jcss.2012.04.003","journal-title":"J. Comput. Syst. Sci."},{"key":"649_CR7","volume-title":"Algorithms and Computation. ISAAC 2011. Lecture Notes in Computer Science","author":"F de Montgolfier","year":"2011","unstructured":"de Montgolfier, F., Soto, M., Viennot, L.: Asymptotic modularity of some graph classes. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) Algorithms and Computation. ISAAC 2011. Lecture Notes in Computer Science, vol. 7074. Springer, Berlin, Heidelberg (2011)"},{"key":"649_CR8","doi-asserted-by":"publisher","unstructured":"Dinh, T.N., Li, X., Thai, M.T.: Network clustering via maximizing modularity: Approximation algorithms and theoretical limits. In: 2015 IEEE International Conference on Data Mining, pp. 101\u2013110 (2015). \nhttps:\/\/doi.org\/10.1109\/ICDM.2015.139","DOI":"10.1109\/ICDM.2015.139"},{"key":"649_CR9","doi-asserted-by":"crossref","unstructured":"Dinh, T.N., Thai, M.T.: Finding community structure with performance guarantees in scale-free networks. In: Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on, pp. 888\u2013891. IEEE (2011)","DOI":"10.1109\/PASSAT\/SocialCom.2011.185"},{"issue":"6","key":"649_CR10","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1109\/JSAC.2013.130602","volume":"31","author":"TN Dinh","year":"2013","unstructured":"Dinh, T.N., Thai, M.T.: Community detection in scale-free networks: approximation algorithms for maximizing modularity. IEEE J. Sel. Areas Commun. 31(6), 997\u20131006 (2013). \nhttps:\/\/doi.org\/10.1109\/JSAC.2013.130602","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"649_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013)"},{"key":"649_CR12","doi-asserted-by":"publisher","unstructured":"Enciso, R., Fellows, M.R., Guo, J., Kanj, I., Rosamond, F., Such\u00fd, O.: What makes equitable connected partition easy. In: Chen, J., Fomin, F.V., (eds.) Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10\u201311, 2009, Revised Selected Papers, pp. 122\u2013133. Springer, Berlin, (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-11269-0_10","DOI":"10.1007\/978-3-642-11269-0_10"},{"key":"649_CR13","unstructured":"Estivill-Castro, V., Fellows, M., Langston, M., Rosamond, F.: FPT is P-time extremal structure I. In: Algorithms and Complexity in Durham 2005, Proceedings of the first ACiD Workshop, volume 4 of Texts in Algorithmics, pp. 1\u201341. King\u2019s College Publications (2005)"},{"issue":"3","key":"649_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75\u2013174 (2010)","journal-title":"Phys. Rep."},{"key":"649_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","volume":"659","author":"S Fortunato","year":"2016","unstructured":"Fortunato, S., Hric, D.: Community detection in networks: a user guide. Phys. Rep. 659, 1\u201344 (2016)","journal-title":"Phys. Rep."},{"key":"649_CR16","unstructured":"Jutla, I.S., Jeub, L.G.S., Mucha, P.J.: A generalized Louvain method for community detection implemented in MATLAB. (2011) \nhttp:\/\/netwiki.amath.unc.edu\/GenLouvain"},{"key":"649_CR17","doi-asserted-by":"publisher","unstructured":"Kawase, Y., Matsui, T., Miyauchi, A.: Additive Approximation Algorithms for Modularity Maximization. In: Hong, S.H. (ed.) 27th International Symposium on Algorithms and Computation (ISAAC 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 64, pp. 43:1\u201343:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.43","DOI":"10.4230\/LIPIcs.ISAAC.2016.43"},{"key":"649_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth\u2014Computations and Approximations,","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth\u2014Computations and Approximations, Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994)"},{"issue":"6","key":"649_CR19","doi-asserted-by":"publisher","first-page":"066122","DOI":"10.1103\/PhysRevE.84.066122","volume":"84","author":"A Lancichinetti","year":"2011","unstructured":"Lancichinetti, A., Fortunato, S.: Limits of modularity maximization in community detection. Phys. Rev. E 84(6), 066122 (2011)","journal-title":"Phys. Rev. E"},{"key":"649_CR20","unstructured":"Lokshtanov, D.: Parameterized integer quadratic programming: Variables and coefficients. (2015) \narXiv:1511.00310\n\n [cs.DS]"},{"key":"649_CR21","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1093\/comnet\/cnx046","volume":"6","author":"C McDiarmid","year":"2017","unstructured":"McDiarmid, C., Skerman, F.: Modularity of regular and treelike graphs. J. Complex Netw. 6, 596 (2017)","journal-title":"J. Complex Netw."},{"key":"649_CR22","unstructured":"McDiarmid, C., Skerman, F.: Modularity of Erd\u0151s-R\u00e9nyi random graphs. Random Struct. Algorithms, (to appear)"},{"key":"649_CR23","unstructured":"McDiarmid, C., Skerman, F.: Modularity of Erd\u0151s-R\u00e9nyi random graphs. In: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, vol. 1 (2018)"},{"issue":"2","key":"649_CR24","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"MEJ Newman","year":"2004","unstructured":"Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)","journal-title":"Phys. Rev. E"},{"issue":"9","key":"649_CR25","first-page":"1082","volume":"56","author":"M Porter","year":"2009","unstructured":"Porter, M., Onnela, J.P., Mucha, P.: Communities in networks. Not AMS 56(9), 1082\u20131097 (2009)","journal-title":"Not AMS"},{"key":"649_CR26","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1016\/j.endm.2017.07.058","volume":"61","author":"LO Prokhorenkova","year":"2017","unstructured":"Prokhorenkova, L.O., Pra\u0142at, P., Raigorodskii, A.: Modularity of models of complex networks. Electron. Notes Discrete Math. 61, 947\u2013953 (2017)","journal-title":"Electron. Notes Discrete Math."},{"key":"649_CR27","unstructured":"Skerman, F.: Modularity of networks. Ph.D. thesis, University of Oxford (2016)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00649-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00649-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00649-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T00:53:04Z","timestamp":1604710384000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00649-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,8]]},"references-count":27,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["649"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00649-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,11,8]]},"assertion":[{"value":"8 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}