Communities

We studied roles, which are nodes clustered together based on their structural position with in the network even though they might in very different parts of the network. Communities on the other hand or the notion of community structure in networks is essentially identifying sets of nodes that are densly connected with each other. Our goal is identifying partitions, groups or communities that are tightly knit within the network.

Granovetter

Now we will try to understand how information flows through the network. Mark Granovetter a social scientist found out that people know about new jobs mostly from acquaintances rather than close friends. One simple explanation is that people usually have more acquaintances than friends. But is there a better, more generic explanation for this phenomenon.

Structural perspective on friendship is that if two nodes have a common friend, they are more likely to become friends themself. And on top of that the interpersonal perspective is that friendship between two people can be strong or weak. Structurally embedded edges are also socially strong with strong bonds. And long ranging edges spanning different parts of the network are socially weak. But Structurally embedded nodes have redundant information, where as long range edges allow us to gather information from different parts of the network and has diverse information.

Clustered nodes with strong edges$\to$ strong friendship

Weak bonds to distinct part of networks $\to$ more diverse information

Triadic Closure implies that two nodes having a common friend are more likely to become friends themselves. And hence might lead to high clustering coefficient.

There is another empirical study by Bearman and Moody shows that teenage girls with low clustering coefficient are more likely to contemplate suicide.

Granovetters observations were empirical study from 1960's, but a recent study from 2007 Onella et al. was a study on phone call network of 20% of some european country with phone call frequency as edge weights. They define Edge overlap $O_{ij}$ between nodes i and j that are connected as the ration of common nodes both i and j have total nodes i and j both have in their neighbourhoods.

Edge overlap $O_{ij}=\frac{|(N(i)\cap N(j))\backslash \{i,j\}|}{|(N(i)\cup N(j))\backslash \{i,j\}|}$

N(i) is the set of neighbors of node i.

Overlap is zero when the edge between i and j is a local bridge. As $O_{ij}$ goes from 0 to 1 their structural friendship gets stronger. Edge overlap represents how strong two nodes are embedded within a network structurally.

When edge overlap is plotted against edge strength, they found that strong edges have stronger overlap. The red dots are for the null network with permuted strengths, where the same strengths are randomly shuffled and assigned to existing edges.

Following plots shows how the size of the giant component changes as edges are removed according to their edge strength and edge overlap respectively.

Red plots are when edges are removed from low edge strength to high edge strength, and black plots are when edges are removed from high edge strength to low edge strength. Likewise in case of edge overlap plot. As you can see in both cases, the network decomposes faster when low strength/low overlap edges are removed first. This is more pronounced in case of edge overlap plot against size of the largest component. As edges with low overlap keep getting removed, the giant component disappears faster. This shows how important weakly connected edges but bring the whole network together and helps with diverse information passing to all corners of the network, even though locally they appear to not that strongly embedded. Hence giving us some validation to Granovetters hypothesis.

Finding Network Communities

We want to detect communities given the network structure and ideally the detected clusters world then correspond to real world groups.

Zachary's Karate club network

This is a famous graph dataset, like MNIST for image classification, you can find it in most python graph libraries. It's a dataset of a karate club members and their relationships within. It has 34 members. A rivalry came up between the coach and one of the club members, the club partitioned into two groups, one going with the original coach and one with the club member. This is a popular dataset for node classification algorithms, community detection and etc.

NCAA Football clubs

Modularity

Modularity $Q$ is measure of how well a network is partitioned into communities. A partition of a network can be thought of as mapping from every node to its respective community. And given the partitioning of the network into disjoint groups $s\in S$

$Q\propto \sum _{s\in S}[\text{(no of edges within s)}-\text{(expected no of edges within s)}]$

We have to build a null model to get the expected no of edges within a group s. Similar to the spokes model we used earlier. We will be building a new network with nodes of same degree distribution, but uniformly random edge connections. Given network $G$ on $n$ nodes and $m$ edges, we have to construct a rewired network $G^{\prime }$. Unlike the spokes model we will allow $G^{\prime }$ to be a multigraph. Two nodes might have more than one edge. By doing this we don't actually have to build the network $G^{\prime }$, and get the expected number of edges within group s analytically.

The expected number of edges between nodes $i$ and $j$ of degrees $k_i$ and $k_j$ is $\frac{k_i{k}_j}{2m}$

We can verify this by calculating the expected total number of edges in $G^{\prime }$ and making sure its the same as $m$

Total expected edges in $G^{\prime }$ = $\frac{1}{2}\sum _{i\in N}\sum _{j\in N}\frac{k_i{k}_j}{2m}=\frac{1}{2}.\frac{1}{2m}\sum _{i\in N}{k}_i(\sum _{j\in N}{k}_j)=\frac{1}{4m}2m.2m=m$

Now that we have the expected edges between i and j in the null model, the modularity of graph G on with partition S is

$Q(G,S)=\frac{1}{2m}\sum _{s\in S}\sum _{i\in s}\sum _{j\in s}(A_{ij}-\frac{k_i{k}_j}{2m})$

Using the indicator function $\delta (c_i,c_j)$ that returns 1 if node 1 and j are in the same community and 0 otherwise, we can also write the modularity Q as follows.

$Q=\frac{1}{2m}\sum _{ij}[A_{ij}-\frac{k_i{k}_j}{2m}]\delta (c_i,c_j)$

We use $2m$ as a normalizing constant, to keep the modularity within -1 and 1. Hence $-1\le Q\le 1$

When Q is positive, the number of edges within groups exceed the expected number. Q within 0.3 and 0.7 means a significant community structure.

Now our goal is to identify communities by maximizing modularity. Find the partition with the maximum modularity.

Louvian Algorithm

We use Louvian algorithm to figure out the partition of a given network with high modularity score. It's a greedy algorithm with run time of $O(n\log n)$ and supports weighted graphs. It also provides hierarchal communities. It's a fast algorithm with high modularity output. Finding the partition with the maximum modularity is NP hard.

Louvian algorithm greedily maximizes modularity starting with each node as its own community. In Phase 1 modularity is optimized by allowing local changes to node-community memberships followed by Phase 2 where identified communities are aggregated into super-nodes to build a new network. These two phases are repeated iteratively until no increase of modularity is possible or enough communities were partitioned from the given network.

Phase 1

We start with each node as its own distinct community. And for each node i, the algorithm performs two calculations:

• Compute the modularity delta $\Delta Q$ when putting node $i$ into the community of some neighbour $j$
• Move $i$ to a community of node $j$ that yields the largest gain in $\Delta Q$

We perform phase 1 until no movement yields a gain. Technically the order of the nodes in which we perform phase 1 affects the output of our algorithm, but empirically the ordering of the nodes does not have significance on the overall modularity that is obtained. We are always moving in such a way the $\Delta Q$ increases and nodes are only in communities with nodes that already have an edge with.

So how do we compute $\Delta Q$ of movie node $i$ to community $C$

It has two components, $\Delta Q(i\to C$ modularity difference in putting node i in C and $\Delta Q(D\to i)$, modularity difference in removing node i from community D

So $\Delta Q=\Delta Q(i\to C)+\Delta Q(D\to C)$ every modularity change includes, a removal of a node from an existing community and putting it in a different community.

$\Delta Q(i\to C)=[\frac{{\sum }_{in}+k_{i,in}}{2m}-{\left(\frac{{\sum }_{tot}+k_i}{2m}\right)}^2]-[\frac{{\sum }_{in}}{2m}-(\frac{{\sum }_{tot}}{2m}{)}^2-\left(\frac{k_i}{2m}{)}^2\right]$

Where

• ${\sum }_{in}$ is sum of link weights between nodes in community $C$
• ${\sum }_{tot}$ is sum of link weights of nodes in community $C$
• $k_{i,in}$ is sum of link weights between node $i$ and community $C$
• $k_i$ is sum of all link weights or degree in case of unweighted graph of node $i$

To understand $\Delta Q(i\to C)$ we will abstract away the network into 3 components, the node $i$ and community $C$ and rest of the network.

$[\frac{{\sum }_{in}+k_{i,in}}{2m}-{\left(\frac{{\sum }_{tot}+k_i}{2m}\right)}^2]$ Modularity contribution after merging node $i$

$[\frac{{\sum }_{in}}{2m}-(\frac{{\sum }_{tot}}{2m}{)}^2-\left(\frac{k_i}{2m}{)}^2\right]$ Modularity contribution before merging node $i$

TODO: more details on Phase 1 of Louvain algorithm.

Phase 2

The communities obtained in the first phase are contracted into super-nodes and the network is created accordingly.

• Super nodes are connected if there is at least one edge between the nodes of the corresponding communities.
• And the weight of the edge between the two super-nodes is the sum of the weights from all edges between their corresponding communities.

And after this new network of supernodes is constructed, we run Phase 1 again.

Notes

Louvain algorithm is not an exact algorithm, we might not get the best possible partition of the graph. It's an approximate algorithm, but very effective and fast and scales to large networks. And figuring out the best partition is an NP hard problem.

Detecting Overlapping Communities: BigCLAM

In reality not all communities will be discrete, a node might belong more than one community and a more generic form of community detection. Your ego network on facebook might have a friend that is both in your highschool community and university community.

For this we will define a generative model for graphs that is based on node community affiliations, also Community Affiliation Graph Model(AGM). And Given a graph $G$, make the assumption that $G$ was generated by our AGM. And find the best parameters for AGM that could have generated $G$ and this way we can discover communities.

Community - Affiliation Graph Model (AGM)

We assume a bipartite graph with communities $C$ as one set of nodes, and our nodes $V$ from graph G as the other set of the nodes in bipartite graph. With membership $M$ into the communities as edges. The AGM is defined as the generation of the graph G by from this bipartite graph. The model also has parameters $p_a,p_b\cdots p_c$ where $p_a$ is the probability that each member of community A has an edge between them. Once we figure out this bipartite graph parameters Nodes $V$, Communities $C$, Memberships $M$ and probabilities $p_a,p_b,\cdots$ we have our Affiliation Graph Model that can generate our graph $G$. This is sort of like folding a bipartite graph but with edges dependent on probabilities.

Given parameters $(V,C,M,\{p_c\})$

• Nodes in community $c$ connect to each other by flipping a coin with probability $p_c$
• And nodes that belong to multiple communities have multiple coin flips, if they miss the first time, they get another chance through the next community. $p(u,v)=1-{\prod }_{c\in M_u\cap M_v}(1-p_c)$. The more groups $u$ and $v$ have in common the more likely there will be an edge between $u$ and $v$.
• If nodes $u$ and $v$ have no communities in common, then $p(u,v)=0$. We resolve this by having a background epsilon community that every node is a member of. This makes it possible for two nodes to have an edge between them, even if they were never part of any communities.

The flexibility of AGM allows us to have all kinds of communities, with no overlap, with overlap, or hierarchical.

So now given a graph $G$ our goal is to find the model $F$ with above parameters $(V,C,M,\{p_c\})$ . The affiliation graph $M$, number of communities $C$ and parameters $p_c$.

We fit our graph $G$ to $F$ and find out the parameters using maximum likelihood estimation

Given real graph $G$ find model/parameters $F$ where ${\mathrm{argmax}}_{F}P(G|F)$, for this we need to be able to compute the probability $P(G|F)$ and then search over $F$ and find out the best possible fit by using things like gradient descent etc.

Graph likelihood $P(G|F)$

Given G and F we calculate likelihood that F generated G: $P(G|F)$

Say F is edge probability matrix and G is our adjacency matrix like below

$F=\left(\begin{array}{cccc}0.25& 0.10& 0.10& 0.04\\ 0.05& 0.15& 0.02& 0.06\\ 0.05& 0.02& 0.15& 0.06\\ 0.01& 0.03& 0.03& 0.09\end{array}\right)G=\left(\begin{array}{cccc}1& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 0& 1& 1\\ 1& 1& 1& 1\end{array}\right)$

$P(G|F)=\prod _{(u,v)\in G}P(u,v)\prod _{(u,v)\notin G}(1-P(u,v))$

product of likelihood of edges in the graph and likelihood of edges not in the graph given edge probabilities $P(u,v)$

We now assume memberships have strengths. Every node $u$ has a membership vector $F_u$ that tells us how strongly u belongs to all the communities. $F_u$ is a row vector of community memberships of node $u$. $F_{uA}$ is the membership strength of node $u$ to community $A$, if its zero then $u$ is not a member of $A$.

Now our goal is find out the community membership vector for all the nodes.

BigCLAM Model

From the above community membership vectors, the probability of nodes $(u,v)$ linking is proportional to the strength of shared memberships.

$P(u,v)=1-\exp (-F_u.F_v^T)$

The strength of the link between u and v will be proportional to how close their memberships to the communities are.

Given a network $G(V,E)$, we maximize the below loss function, which is a logarithm applied to the likelihood function $P(G|F)$ we defined earlier.

$l(F)=\sum _{(u,v)\in E}\log (1-\exp (-F_u{F}_v^T))-\sum _{(u,v)\notin E}{F}_u{F}_v^T$

Optimization steps:

• Start with random $F$
• Update $F_{uC}$ for node $u$ while fixing the memberships of all other nodes.
• Updating takes linear time in the degree of $u$

Gradient ascent

$\Delta l(F_u)=\sum _{v\in \mathcal{N}(u)}{F}_v\frac{exp(-F_u{F}_v^T)}{1-exp(-F_u{F}_v^T)}-\sum _{v\in \mathcal{N}(u)}{F}_v$

We perform gradient ascent using above gradient, where we make small changes to F that lead to increase in log-likelihood.

Pure gradient ascent is slow, so we can cache $F_v$ using the following to makes it linear time in the degree of $u$

$\sum _{v\notin \mathcal{N}(u)}{F}_v=(\sum _v{F}_v-F_u-\sum _{v\in \mathcal{N}(u)}{F}_v)$

Chapters

1. Introduction, Structure of Graphs
2. Properties of Networks and Random Graph Models
3. Motifs and Structural Roles in Networks
4. Community Structure in Networks
5. Spectral Clustering
6. Message Passing and Node Classification
7. Graph Representation Learning
8. Graph Neural Networks
9. Graph Neural Networks - Pytorch Geometric
10. Deep Generative Models for Graphs
11. Link Analysis: PageRank
12. Network Effects and Cascading Behaviour
13. Probabilistic Contagion and Models of Influence
14. Influence Maximization in Networks
15. Outbreak Detection in Networks
16. Network Evolution
17. Reasoning over Knowledge Graphs
18. Limitations of Graph Neural Networks
19. Applications of Graph Neural Networks