{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:22:26Z","timestamp":1762323746633,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,10,7]]},"abstract":"<jats:p>We examine the problem of identifying social circles, or sets of cohesive and mutually aware nodes surrounding an initial query set, in directed graphs where the complete graph is not known beforehand. This problem differs from local community mining, in that the query set defines the circle of interest. We explicitly handle edge direction, as in many cases relationships are not symmetric, and focus on the local context because many real-world graphs cannot be feasibly known. We outline several issues that are unique to this context, introduce a quality function to measure the value of including a particular node in an emerging social circle, and describe a greedy social circle discovery algorithm. We demonstrate the effectiveness of this approach on artificial benchmarks, large networks with topical community labels, and several real-world case studies.<\/jats:p>","DOI":"10.1145\/2641759","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T12:08:55Z","timestamp":1409054935000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Discovering Social Circles in Directed Graphs"],"prefix":"10.1145","volume":"8","author":[{"given":"Scott H.","family":"Burton","sequence":"first","affiliation":[{"name":"Brigham Young University, Idaho"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe G.","family":"Giraud-Carrier","sequence":"additional","affiliation":[{"name":"Brigham Young University, Provo, UT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09182"},{"key":"e_1_2_1_2_1","unstructured":"I. Ajzen and M. Fishbein. 1980. Understanding Attitudes and Predicting Social Behavior. Prentice-Hall Inc. Englewood Cliffs NJ.  I. Ajzen and M. Fishbein. 1980. Understanding Attitudes and Predicting Social Behavior. Prentice-Hall Inc. Englewood Cliffs NJ."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135814"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"J. P. Bagrow. 2008. Evaluating local community methods in networks. Journal of Statistical Mechanics: Theory and Experiment (2008) P05001.  J. P. Bagrow. 2008. Evaluating local community methods in networks. Journal of Statistical Mechanics: Theory and Experiment (2008) P05001.","DOI":"10.1088\/1742-5468\/2008\/05\/P05001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.046108"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427995_3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.056119"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"A. Capocci V. D. P. Servedio G. Caldarelli and F. Colaiori. 2005. Detecting communities in large networks. Physica A: Statistical Mechanics and its Applications 352 2--4 (2005) 669--676.  A. Capocci V. D. P. Servedio G. Caldarelli and F. Colaiori. 2005. Detecting communities in large networks. Physica A: Statistical Mechanics and its Applications 352 2--4 (2005) 669--676.","DOI":"10.1016\/j.physa.2004.12.050"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CASoN.2009.29"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.026132"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2009.06.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014068"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.989932"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_17_1","unstructured":"A. Friggeri G. Chelius and E. Fleury. 2011. Egomunities exploring socially cohesive person-based communities. CoRR (http:\/\/arxiv.org\/abs\/1102.2623) abs\/1102.2623 (2011).  A. Friggeri G. Chelius and E. Fleury. 2011. Egomunities exploring socially cohesive person-based communities. CoRR (http:\/\/arxiv.org\/abs\/1102.2623) abs\/1102.2623 (2011)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom.2010.24"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/10\/103018"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/2091658"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2092880"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.81.016103"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016118"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/11\/3\/033015"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557074"},{"volume-title":"The 4th SNA-KDD Workshop (SNA-KDD","year":"2010","author":"Lee C.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.066107"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.118703"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.3233\/WIA-2008-0147"},{"key":"e_1_2_1_31_1","unstructured":"J. McAuley and J. Leskovec. 2012. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems 25 P. Bartlett F. C. N. Pereira C. J. C. Burges L. Bottou and K. Q. Weinberger (Eds.). 548--556. http:\/\/books.nips.cc\/papers\/files\/nips25\/NIPS2012_0272.pdf.  J. McAuley and J. Leskovec. 2012. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems 25 P. Bartlett F. C. N. Pereira C. J. C. Burges L. Bottou and K. Q. Weinberger (Eds.). 548--556. http:\/\/books.nips.cc\/papers\/files\/nips25\/NIPS2012_0272.pdf."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718519"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys2162"},{"key":"e_1_2_1_36_1","first-page":"6","article-title":"Fast algorithm for detecting community structure in networks","volume":"69","author":"Newman M. E. J.","year":"2004","journal-title":"Physical Review E"},{"volume-title":"Proceedings of 3rd IEEE International Conference on Social Computing. 35--40","author":"Nguyen N. P.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2009\/03\/P03024"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_40_1","unstructured":"S. Papadopoulos A. Skusa A. Vakali Y. Kompatsiaris and N. Wagner. 2009. Bridge bounding: A local approach for efficient community discovery in complex networks. Arxiv preprint arXiv:0902.0871 (2009).  S. Papadopoulos A. Skusa A. Vakali Y. Kompatsiaris and N. Wagner. 2009. Bridge bounding: A local approach for efficient community discovery in complex networks. Arxiv preprint arXiv:0902.0871 (2009)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11569596_31"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.64"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.016110"},{"key":"e_1_2_1_45_1","unstructured":"M. Rosenberg. 1989. Society and the Adolescent Self-Image (rev). Wesleyan University Press Middletown CT.  M. Rosenberg. 1989. Society and the Adolescent Self-Image (rev). Wesleyan University Press Middletown CT."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"volume-title":"Group Dynamics: The Psychology of Small Group Behavior","year":"1976","author":"Shaw M. E.","key":"e_1_2_1_47_1"},{"volume-title":"Proceedings of the 5th SIAM International Conference on Data Mining. 76--84","author":"Smyth S.","key":"e_1_2_1_48_1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.046102"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0277-9536(00)00116-7"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150448"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.48"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"S. Wasserman and K. Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press New York and Cambridge UK.  S. Wasserman and K. Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press New York and Cambridge UK.","DOI":"10.1017\/CBO9780511815478"},{"volume-title":"Into the Blogosphere: Rhetoric, Community, and Culture in Weblogs","author":"Wei C.","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.139"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"volume-title":"Proceedings of the 6th SNA-KDD Workshop on Social Network Mining and Analysis.","author":"Yang J.","key":"e_1_2_1_58_1"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.publhealth.20.1.287"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2641759","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2641759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:19Z","timestamp":1750229779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2641759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,10,7]]}},"alternative-id":["10.1145\/2641759"],"URL":"https:\/\/doi.org\/10.1145\/2641759","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}