Actions

Difference between revisions of "Networks Community Detection"

From OPOSSEM

(Introduction)
(Graph Partitioning)
Line 10: Line 10:
  
 
From the outset, we are faced with the problem of articulating a good, quantitative definition of what a community is.  Since the network primarily encodes the structure of the community, this is where we focus our attention.  ''Modularity'', discussed in greater detail next, is the operational definition of what a good community is and, therefore, serves as the basis for nearly all community detection algorithms.
 
From the outset, we are faced with the problem of articulating a good, quantitative definition of what a community is.  Since the network primarily encodes the structure of the community, this is where we focus our attention.  ''Modularity'', discussed in greater detail next, is the operational definition of what a good community is and, therefore, serves as the basis for nearly all community detection algorithms.
 +
 +
=Modularity=
 +
Consider the patterns of connectivity within a community of people.  What kinds of structural features might we expect to observe among these individuals?  On plausible feature is that there is a higher degree of connectivity (more edges) among these individuals than we would observe for any random collection of people.  This is the intuition that modularity captures.
 +
 +
Given an assignment of nodes to communities, modularity will return a value between -1 and 1 indicating whether there is less (< 0) or more (> 0) connectivity among the individuals belonging to the communities that would be expected at random.  In community detection, we're seeking an assignment of nodes to communities that maximizes the modularity of the network - since an increase in modularity indicates that we have found labeling that increases the connectivity within the communities.
  
 
=Graph Partitioning=
 
=Graph Partitioning=

Revision as of 12:00, 8 July 2011


Objectives

  • Understand the difference between graph partitioning and community detection
  • Survey the different methods available for community detection

Introduction

Algorithms for finding communities have many uses in network science, particularly in the social sciences. Since collective action is such a fundamental aspect of social and political behavior, identifying the groups to which individuals belong is an important task. Here we discuss a variety of methods for approaching this problem.

From the outset, we are faced with the problem of articulating a good, quantitative definition of what a community is. Since the network primarily encodes the structure of the community, this is where we focus our attention. Modularity, discussed in greater detail next, is the operational definition of what a good community is and, therefore, serves as the basis for nearly all community detection algorithms.

Modularity

Consider the patterns of connectivity within a community of people. What kinds of structural features might we expect to observe among these individuals? On plausible feature is that there is a higher degree of connectivity (more edges) among these individuals than we would observe for any random collection of people. This is the intuition that modularity captures.

Given an assignment of nodes to communities, modularity will return a value between -1 and 1 indicating whether there is less (< 0) or more (> 0) connectivity among the individuals belonging to the communities that would be expected at random. In community detection, we're seeking an assignment of nodes to communities that maximizes the modularity of the network - since an increase in modularity indicates that we have found labeling that increases the connectivity within the communities.

Graph Partitioning

Label Propagation

Edge Betweenness

Conclusion

References

<references group=""></references>

Discussion questions

Problems

Glossary

  • [[Def: ]]
  • [[Def: ]]
  • [[Def: ]]