{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T05:53:16Z","timestamp":1717653196443},"reference-count":39,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2014,8]]},"abstract":" The last decade has witnessed an explosion in the modeling of complex systems. Predominantly, graphs are used to represent these systems. The problem of detecting overlapping clusters in graphs is of utmost importance. We present a novel definition of overlapping clusters. A noncooperative game is proposed such that the equilibrium conditions of the game correspond to the clusters in the graph. Several properties of the game are analyzed and exploited to show the existence of a pure Nash equilibrium (NE) and compute it effectively. We present two algorithms to compute NE and prove their convergence. Empirically, the running times of both algorithms are nearly linear in the number of edges. Also, one of the algorithms can be readily parallelized, making it scalable. Finally, our approach is compared with existing overlapping cluster detection algorithms and validated on several artificial and real data sets. <\/jats:p>","DOI":"10.1287\/ijoc.2013.0588","type":"journal-article","created":{"date-parts":[[2014,4,29]],"date-time":"2014-04-29T17:53:10Z","timestamp":1398793990000},"page":"629-643","source":"Crossref","is-referenced-by-count":10,"title":["A Game-Theoretic Approach to Graph Clustering"],"prefix":"10.1287","volume":"26","author":[{"given":"Supreet","family":"Mandala","sequence":"first","affiliation":[{"name":"Department of Industrial and Manufacturing Engineering, Pennsylvania State University, University Park, Pennsylvania 16802"}]},{"given":"Soundar","family":"Kumara","sequence":"additional","affiliation":[{"name":"Department of Industrial and Manufacturing Engineering, Pennsylvania State University, University Park, Pennsylvania 16802"}]},{"given":"Kalyan","family":"Chatterjee","sequence":"additional","affiliation":[{"name":"Department of Economics, Pennsylvania State University, State College, Pennsylvania 16801"}]}],"member":"109","reference":[{"issue":"1","key":"B1","first-page":"374","volume":"13","author":"Brown GW","year":"1951","journal-title":"Activity Anal. Production Allocation"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-008-0108-3"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.08.004"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1109\/34.745730"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0186-6"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2010.05.046"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74976-9_12"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87479-9_45"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/10\/103018"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348559"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016118"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/11\/3\/033015"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0011976"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0018961"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1007\/11871637_60"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00091-7"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.77.016107"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2004-00128-7"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/6\/186"},{"key":"B27","first-page":"1","volume-title":"Neural Inform. Processing Systems Conf. Workshop (NIPS 2009)","author":"Pelillo M","year":"2009"},{"key":"B28","first-page":"87","volume-title":"Interdisciplinary Statist. Bioinformatics: Proc.","author":"Pinney DR","year":"2006"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"issue":"3","key":"B31","first-page":"75","volume":"486","author":"Santo F","year":"2010","journal-title":"Phys. Rep."},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1109\/21.293490"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2009\/07\/P07042"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2008.12.021"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2006.130"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2008.4761386"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78849-2_7"},{"key":"B38","author":"Xie J","year":"2011","journal-title":"CoRR"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2011.154"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2006.07.023"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2013.0588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T13:09:13Z","timestamp":1680440953000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2013.0588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1287\/ijoc.2013.0588"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2013.0588","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8]]}}}