Communities in Networks

Networks are “groupy”

  • Network formation processes lead to “groupy” networks
  • Foci (Scott Feld)
  • Triadic closure
  • Homophily

We may want to identify groups

  • Understanding where information is likely to flow / be held in common
  • Social media marketers identifying “interest groups”
  • Researchers understanding a scientific field
  • Understanding relationships between groups

Early approaches to identify groups

  • Components
    • Everyone connected in any way
    • Usually not useful - (nearly) everyone is connected
  • Cliques
    • Everyone is connected to everyone else in group
    • Expanded to n-cliques (everyone in group is at a distance of n or less from everyone else)
    • Long, stringy groupings

Clique Example

Early approaches (continued)

  • K-plexes
    • All members of group are connected to all but k other members

Modern approaches - community detection

  • Modularity
    • Maximize edges within communities and minimize edges between them
  • Agglomeration
    • Add nodes/groups that are closely connected
  • Reduction
    • Remove edges with high betweenness
  • Random walk
    • “Walk” through the network many times
  • Often quite similar

Fast Greedy Example

Core and Periphery

Many groups have a core and a periphery

  • New people start on the periphery (Legitimate Peripheral Participation)
  • People leaving move to the periphery
  • Different levels of dedication / resources
  • Evolutionary perspective
    • In order for groups to survive, there has to be a core


  • Those in core more likely to have knowledge, experience, and to stick around
  • Identify the most dedicated group
  • Identify those in danger of leaving / needing help

Ways of measuring

  • Block modeling

Ways of measuring

  • K-cores
    • Every node gets a value: the largest k where they are in a subgraph where everyone else has degree of at least k
  • Rich-club coefficient
    • How much are those with high degree connected to each other