2012 OntheSeparabilityofStructuralCl: Difference between revisions

From GM-RKB
Jump to navigation Jump to search
(Importing text file)
 
m (Text replacement - " ↵↵" to " ")
 
(21 intermediate revisions by 3 users not shown)
Line 1: Line 1:
* ([[2012_OntheSeparabilityofStructuralCl|Abrahao & al, 2012]]) ⇒ [[author::Bruno Abrahao]], [[author::Sucheta Soundarajan]], [[author::John Hopcroft]], and [[author::Robert Kleinberg]]. ([[year::2012]]). "On the Separability of Structural Classes of Communities." In: [[proceedings::Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining]] ([[conference::KDD-2012]]). ISBN:978-1-4503-1462-6 [http://dx.doi.org/10.1145/2339530.2339631 doi:10.1145/2339530.2339631]  
* ([[2012_OntheSeparabilityofStructuralCl|Abrahao et al., 2012]]) [[author::Bruno Abrahao]], [[author::Sucheta Soundarajan]], [[author::John Hopcroft]], and [[author::Robert Kleinberg]]. ([[year::2012]]). “On the Separability of Structural Classes of Communities.In: [[proceedings::Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining]] ([[conference::KDD-2012]]). ISBN:978-1-4503-1462-6 [http://dx.doi.org/10.1145/2339530.2339631 doi:10.1145/2339530.2339631]


<B>Subject Headings:</B>  
<B>Subject Headings:</B>


==Notes==
== Notes ==


==Cited By==
==Cited By==
Line 9: Line 9:
* http://dl.acm.org/citation.cfm?id=2339530.2339631&preflayout=flat#citedby
* http://dl.acm.org/citation.cfm?id=2339530.2339631&preflayout=flat#citedby


==Quotes==
== Quotes ==
===Author Keywords===
 
=== Author Keywords ===
* [[Class separability]]; [[community structure]]; [[design methodology]]; [[detection algorithm]]s; [[network]]s
* [[Class separability]]; [[community structure]]; [[design methodology]]; [[detection algorithm]]s; [[network]]s


===Abstract===
=== Abstract ===


Three major [[factor]]s govern the [[intricacies of community extraction in network]]s: (1) the application domain includes a wide variety of [[network]]s of fundamentally different natures, (2) the [[literature]] offers a [[multitude of disparate community detection algorithm]]s, and (3) there is no consensus characterizing how to [[discriminate communiti]]es from [[non-communiti]]es. </s>
Three major [[factor]]s govern the [[intricaci]]es of [[community extraction]] in [[network]]s: (1) the [[application domain]] includes a wide variety of [[network]]s of fundamentally different natures, (2) the [[literature]] offers a multitude of disparate [[community detection algorithm]]s, and (3) there is no [[consensus]] characterizing how to [[discriminate communiti]]es from [[non-communiti]]es. </s>
In [[this paper]], we present a comprehensive [[analysis of community properti]]es through a [[class separability framework]]. </s>
[[In this paper, we]] present a comprehensive [[analysis]] of [[community properti]]es through a [[class separability framework]]. </s>
[[Our approach]] enables the assessement of the [[structural dissimilarity]] among the [[output of multiple community detection algorithm]]s and between the output of [[algorithm]]s and communities that arise in practice. </s>
[[Our approach]] enables the [[assessement]] of the [[structural dissimilarity]] among the [[output]] of multiple [[community detection algorithm]]s and between the [[output]] of [[algorithm]]s and [[communiti]]es that arise in practice. </s>
To [[demostrate this concept]], we furnish [[our method]] with a [[large set]] of [[structural properti]]es and [[multiple community detection algorithm]]s. </s>
To [[demostrate this concept]], we furnish [[our method]] with a [[large set]] of [[structural properti]]es and multiple [[community detection algorithm]]s. </s>
Applied to a diverse [[collection]] of [[large scale network dataset]]s, the analysis reveals that (1) the different [[detection algorithms extract]] fundamentally different structures; (2) the [[structure of communiti]]es that arise in practice is closest to that of communities that [[random-walk-based algorithms extract]], although still siginificantly different from that of the [[output]] of all [[the algorithm]]s; and (3) a small [[subset]] of the [[properti]]es are nearly as [[discriminative]] as the [[full set]], while making explicit the ways in which the [[algorithm]]s produce biases. </s>
Applied to a diverse [[collection]] of [[large scale]] [[network dataset]]s, the analysis reveals that (1) the different [[detection algorithm]]s extract fundamentally different structures; (2) the [[structure of communiti]]es that arise in practice is closest to that of [[communiti]]es that [[random-walk-based algorithm]]s extract, although still siginificantly different from that of the [[output]] of all the [[algorithm]]s; and (3) a small [[subset]] of the [[properti]]es are nearly as [[discriminative]] as the full [[set]], while making explicit the ways in which the [[algorithm]]s produce [[bias]]es. </s>
[[Our framework]] enables an [[informed choice]] of the most [[suitable community detection method]] for a given purpose and [[network]] and allows for a [[comparison of existing community detection algorithm]]s while guiding the [[design]] of new ones. </s>
[[Our framework]] enables an [[informed choice]] of the most suitable [[community detection method]] for a given purpose and [[network]] and allows for a comparison of existing [[community detection algorithm]]s while guiding the [[design]] of new ones. </s>


==References==
== References ==
{{#ifanon:|
{{#ifanon:|
* 1. David W. Aha, Dennis Kibler, Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [http://dx.doi.org/10.1023/A:1022689900470 doi:10.1023/A:1022689900470]
* 1. David W. Aha, Dennis Kibler, Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [http://dx.doi.org/10.1023/A:1022689900470 doi:10.1023/A:1022689900470]
* 2. Y. Ahn, J. P. Bagrow, and S. Lehmann. Link Communities Reveal Multiscale Complexity in Networks. Nature, 466(7307):761--764, 2010.
* 2. Y. Ahn, J. P. Bagrow, and S. Lehmann. Link Communities Reveal Multiscale Complexity in Networks. Nature, 466(7307):761--764, 2010.
* 3. Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, Xiangyang Lan, Group Formation in Large Social Networks: Membership, Growth, and Evolution, Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 20-23, 2006, Philadelphia, PA, USA [http://doi.acm.org/10.1145/1150402.1150412 doi:10.1145/1150402.1150412]
* 3. [[Lars Backstrom]], Dan Huttenlocher, [[Jon Kleinberg]], Xiangyang Lan, Group Formation in Large Social Networks: Membership, Growth, and Evolution, Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 20-23, 2006, Philadelphia, PA, USA [http://doi.acm.org/10.1145/1150402.1150412 doi:10.1145/1150402.1150412]
* 4. V. D. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre. Fast Unfolding of Communities in Large Networks. Mar. 2008. Journal of Statistical Mechanics.
* 4. V. D. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre. Fast Unfolding of Communities in Large Networks. Mar. 2008. Journal of Statistical Mechanics.
* 5. F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, Dec. 1996.
* 5. F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, Dec. 1996.
Line 36: Line 37:
* 11. M. A. Hall. Correlation-based Feature Subset Selection for Machine Learning. PhD Thesis, Department of Computer Science, University of Waikato, 1999.
* 11. M. A. Hall. Correlation-based Feature Subset Selection for Machine Learning. PhD Thesis, Department of Computer Science, University of Waikato, 1999.
* 12. S. Hoory, N. Linial, and A. Wigderson. Expander Graphs and their Applications. Bulletin of the American Mathematical Society, 43(4):439, 2006.
* 12. S. Hoory, N. Linial, and A. Wigderson. Expander Graphs and their Applications. Bulletin of the American Mathematical Society, 43(4):439, 2006.
* 13. George Karypis, Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [http://dx.doi.org/10.1137/S1064827595287997 doi:10.1137/S1064827595287997]
* 13. George Karypis, [[Vipin Kumar]], A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [http://dx.doi.org/10.1137/S1064827595287997 doi:10.1137/S1064827595287997]
* 14. B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. The Bell System Technical Journal, 49(1):291--307, 1970.
* 14. B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. The Bell System Technical Journal, 49(1):291--307, 1970.
* 15. A. Lancichinetti and S. Fortunato. Community Detection Algorithms: A Comparative Analysis. Physical Review E, 80:056117, Nov 2009.
* 15. A. Lancichinetti and S. Fortunato. Community Detection Algorithms: A Comparative Analysis. Physical Review E, 80:056117, Nov 2009.
* 16. Jure Leskovec, Lada A. Adamic, Bernardo A. Huberman, The Dynamics of Viral Marketing, Proceedings of the 7th ACM Conference on Electronic Commerce, p.228-237, June 11-15, 2006, Ann Arbor, Michigan, USA [http://doi.acm.org/10.1145/1134707.1134732 doi:10.1145/1134707.1134732]
* 16. [[Jure Leskovec]], Lada A. Adamic, Bernardo A. Huberman, The Dynamics of Viral Marketing, Proceedings of the 7th ACM Conference on Electronic Commerce, p.228-237, June 11-15, 2006, Ann Arbor, Michigan, USA [http://doi.acm.org/10.1145/1134707.1134732 doi:10.1145/1134707.1134732]
* 17. Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, Michael W. Mahoney, Statistical Properties of Community Structure in Large Social and Information Networks, Proceedings of the 17th International Conference on World Wide Web, April 21-25, 2008, Beijing, China [http://doi.acm.org/10.1145/1367497.1367591 doi:10.1145/1367497.1367591]
* 17. [[Jure Leskovec]], Kevin J. Lang, Anirban Dasgupta, Michael W. Mahoney, Statistical Properties of Community Structure in Large Social and Information Networks, Proceedings of the 17th International Conference on World Wide Web, April 21-25, 2008, Beijing, China [http://doi.acm.org/10.1145/1367497.1367591 doi:10.1145/1367497.1367591]
* 18. Jure Leskovec, Kevin J. Lang, Michael Mahoney, Empirical Comparison of Algorithms for Network Community Detection, Proceedings of the 19th International Conference on World Wide Web, April 26-30, 2010, Raleigh, North Carolina, USA [http://doi.acm.org/10.1145/1772690.1772755 doi:10.1145/1772690.1772755]
* 18. [[Jure Leskovec]], Kevin J. Lang, Michael Mahoney, Empirical Comparison of Algorithms for Network Community Detection, Proceedings of the 19th International Conference on World Wide Web, April 26-30, 2010, Raleigh, North Carolina, USA [http://doi.acm.org/10.1145/1772690.1772755 doi:10.1145/1772690.1772755]
* 19. R. Lyons and Y. Peres. Probability on Trees and Networks. Cambridge University Press, 2012.
* 19. R. Lyons and Y. Peres. Probability on Trees and Networks. Cambridge University Press, 2012.
* 20. N. Mishra, R. Schreiber, I. Stanton, and R. Tarjan. Finding Strongly Knit Clusters in Social Networks. Internet Mathematics, 5(1):155--174, Jan. 2008.
* 20. N. Mishra, R. Schreiber, I. Stanton, and R. Tarjan. Finding Strongly Knit Clusters in Social Networks. Internet Mathematics, 5(1):155--174, Jan. 2008.

Latest revision as of 19:33, 20 December 2023

Subject Headings:

Notes

Cited By

Quotes

Author Keywords

Abstract

Three major factors govern the intricacies of community extraction in networks: (1) the application domain includes a wide variety of networks of fundamentally different natures, (2) the literature offers a multitude of disparate community detection algorithms, and (3) there is no consensus characterizing how to discriminate communities from non-communities. In this paper, we present a comprehensive analysis of community properties through a class separability framework. Our approach enables the assessement of the structural dissimilarity among the output of multiple community detection algorithms and between the output of algorithms and communities that arise in practice. To demostrate this concept, we furnish our method with a large set of structural properties and multiple community detection algorithms. Applied to a diverse collection of large scale network datasets, the analysis reveals that (1) the different detection algorithms extract fundamentally different structures; (2) the structure of communities that arise in practice is closest to that of communities that random-walk-based algorithms extract, although still siginificantly different from that of the output of all the algorithms; and (3) a small subset of the properties are nearly as discriminative as the full set, while making explicit the ways in which the algorithms produce biases. Our framework enables an informed choice of the most suitable community detection method for a given purpose and network and allows for a comparison of existing community detection algorithms while guiding the design of new ones.

References

;

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2012 OntheSeparabilityofStructuralClJohn E. Hopcroft
Bruno Abrahao
Sucheta Soundarajan
Robert Kleinberg
On the Separability of Structural Classes of Communities10.1145/2339530.23396312012