CS224W Machine Learning with Graphs

Lecture 4

Title: Community Structure in Networks
Date: 2020. 04. 03 (FRI) ~ 2020. 04. 06 (MON)
Materials: Slides YouTube

Networks and Communities

• Roles(RoIX) based on the feature, Communities(Fast Modularity) based on cluster

Flow of Information

• Questions
  • How does information flow through the network?
  • How do people find out about new job?
    • Contacts were often acquaintances(less than friends)¹ rather than close friends

• Granovetter’s Answer

  • Link perspectives: Structural perspective and Interpersonal perspective
  • Structural role(Triadic Closure)
    • Structure: Well-embedded edges are socially strong
    • Information: Well-embedded heavily redundant in terms of² information access
      • Through the weak connection, the node can get newer information which can’t get the well-embedded parts
      • So, in the job seeking problem, people contact to acquaintances rather than friends
    • Strong structure(Socially Strong) means each neighbors are also neighbors of others
      • Weight of edge means interpersonal strength
    • Triadic Closure means High clustering coefficient

  

• Edge overlap

  • The ratio of the # of mutual friends and # of union friends
  • Overlap = 0 means an edge is a local bridge

• Edge Removal

  • By Strength: The network structure are decomposed faster when remove low # of weighted edge than high
  • By Overlap: The network structure are decomposed faster when remove low edge overlap than high

Network Communities

• Definition
  • Sets of tightly connected nodes
  • Sets of nodes with lots of internal connections and few external ones

• Communities can exchange clusters, groups and modules

• Zachary’s Karate club network(Social Network Data Example)
  • In the network, there are two different karate club
  • Split could be explained by a minimum cut in the network

Modularity $Q$

• How well as network is partitioned into communities
• $Q \propto \sum_{\{s\}\in{S}}[($ # edges within group $s)$ - $($expected # edges within group $s)]$
  • To calculated expected # edges with group, need a null model
  • Null Model(Configuration Model)
    • The expected # of edges between nodes $i$ and $j$
    • ${k_i \cdot k_j} \over {2m}$ ($k_i, K_j$ means degrees $i$ and $j$)
• Modularity of partitioning $S$ of graph $G$
  • $$Q(G,S) = {\{1\}\over{2m}}\sum_{\{s\}\in{S}}\sum_{\{i\}\in{s}}\sum_{\{j\}\in{s}}(A_{ij} - {\{k_ik_j\}\over{2m}})$$
  • where $A_{ij}$ = 1 if $i$ -> j 0 otherwise
• Modularity values take range [-1, 1]
  • $Q$ greater than 0.3 - 0.7 means significant community structure
  • Negative $Q$ means anti-communities
    • Positive $Q$ means that nodes in the same communities are connected stronger than the null model (More connection than the null model)
    • If $Q = 0$, this community doesn’t a difference with random connection. However, if $Q > 0$, this community have more connections(edges) than the random model.
• We can identify communities by maximizing modularity

Louvain Algorithm

• Using Greedy algorithm for community detection(Greedily maximizes modularity)

  • Using to study large networks
  • Fast, Rapid convergence, High modularity output

• Steps

  1. Optimize modularity by local changes to node-communities memberships
     • Changing community of each node, calculate modularity delta($\Delta{Q}$)
       • Possible communities to change are only neighbor of node
       • $$\Delta{Q} = \Delta{Q({i}\to{C})} + \Delta{Q({D}\to{i})}$$
       • Modularity delta means the aggregation of change of modularity when node $i$ put into community $C$ and change of modularity when node $i$ pull from community $D$
     • The nodes’ community determine the community with maximum modularity
     • Repeat until no increase modularity
  2. Aggregate nodes to super-nodes to build a new network
  3. Repeat these two steps until no increase of modularity

  

Detecting Overlapping Communities: BigCLAM

1. Define generative model for graphs

   • Community Affiliation Graph Model(AGM)

2. Discover communities

   • Given graph G, make the assumption that G was generated by AGM

   • Find the best AGM = discover communities

Community Affiliation Graph Model(AGM)

• $$V, C, M, \{p_c\}$$

• $V$: Nodes

• $C$: Communities

• $M$: Memberships, The link between nodes and communities

• $P_c$: The probability that Node $v$ has Membership $m$ to Community $c$

To detect communities with AGM

• Given a Graph, find the model $F$

• Terms
  • $M$: Affiliation graph
  • $C$: Number of communities like $k$ in k-means
  • $p_c$: Parameters
• Maximum likelihood estimation
  • $$arg_F max P(G|F)$$
  • $$P(G|F) = \prod_{\{(u,v)\}\in{G}}P(u,v)\prod_{\{(u,v)\notin{G}\}}(1-P(u, v))$$
• Membership has strengths ($F_{uA}$)
  • How strong connect node to community
  • $F_{uA} = 0$ means that node $u$ is not a member of community $A$