brain of mat kelcey...

e10.4 communities in social graphs

October 06, 2009 at 08:05 PM | categories: Uncategorized

social graphs, like twitter or facebook, often follow the pattern of having clusters of highly connected components with an occasional edge joining these clusters.

these connecting edges define the boundaries of communities in the social network and can be identified by algorithms that measure betweenness.

the girvan-newman algorithm can be used to decompose a graph hierarchically based on successive removal of the edges with the highest betweenness.

the algorithm is basically

  1. calculate the betweenness of each edge (using an all shortest paths algorithm)
  2. remove the edge(s) with the highest betweenness
  3. check for connected components (using tarjan's algorithm)
  4. repeat for graph or subgraphs if graph was split