Difference between revisions of "Leskovec www 2010"

From Cohen Courses
Jump to navigationJump to search
(Created page with '== Citation == Leskovec, J., K. J Lang, and M. Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th international confere…')
 
 
Line 6: Line 6:
  
 
== Summary ==
 
== Summary ==
−
This [[Category::paper]] presents an approach to [[AddressesProblem::Network Community Detection]]. Here they try to answer the question of network evolution of over time. While static graph models have been studied, less is known about time-evolving graphs. They use the following [[UsesDataset::US_Patent_citation_dataset|Patent Citation Network]]. They study a number of real world graphs and observe some interesting phenomena.
+
This [[Category::paper]] presents an empirical evaluation of algorithms for the problem of [[AddressesProblem::Network Community Detection]]. They use 40 different real world networks, compare 12 objective functions and 8 approximation algorithms and report their findings.  
  
−
* Most graphs densify over time with number of edges growing superlinearly with respect to the number of nodes
+
* They find that network detection for large graphs can be surprisingly intricate
−
* The average distance between nodes shrinks over time
+
* They find that most methods exhibit qualitatively similar behavior
−
 
+
* However depending on the objective certain kinds of clusters tend to be preferred which the authors refer to as systematic biases of the method.
−
Since existing graph generation models do not model for such behaviors they propose a new graph generation model based on a '''forestfire''' approach.
+
* The authors suggest that a regularization like approach would help correct for the specific deficiencies of the methods.
−
 
 
−
== Method ==
 
−
They use the [[UsesMethod::Forest Fire graph generation|Forest Fire]] method for graph generation. The goal of this method to construct a graph that has the properties of following densification power laws, long-tailed in and out degrees and shrinking diameter.
 

Latest revision as of 23:14, 16 February 2011

Citation

Leskovec, J., K. J Lang, and M. Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th international conference on World wide web, 631–640.

Online version

WWW 2010

Summary

This paper presents an empirical evaluation of algorithms for the problem of Network Community Detection. They use 40 different real world networks, compare 12 objective functions and 8 approximation algorithms and report their findings.

  • They find that network detection for large graphs can be surprisingly intricate
  • They find that most methods exhibit qualitatively similar behavior
  • However depending on the objective certain kinds of clusters tend to be preferred which the authors refer to as systematic biases of the method.
  • The authors suggest that a regularization like approach would help correct for the specific deficiencies of the methods.
Retrieved from "http://curtis.ml.cmu.edu/w/courses/index.php?title=Leskovec_www_2010&oldid=4397"