
Retweet network of political hashtags prior to the 2010 US election.
Limitations of Visualization: In many small systems, visualization alone may not reveal clusters, necessitating algorithms that can automatically detect them. ## Echo Chambers
Echo Chambers and Filter Bubbles:

Social Networks: Groups of friends or followers on platforms like Facebook or Twitter, where members interact more frequently with each other than with outsiders.
Biological Networks: Functional groups of proteins in a cell that work together to perform specific biological processes.
Transportation Networks: Clusters of interconnected airports or train stations that facilitate regional travel more than long-distance connections.
Citation Networks: Academic papers that frequently cite each other, forming a community of related research topics.
Online Platforms: Subreddits or online forums where users with shared interests engage in discussions more often within the group than outside it.
Economic Networks: Companies within the same industry that trade more frequently with each other than with companies in other sectors.
Region of Maximal local densityrelatively higher connection density within the cluster than between the clustersHigh intra-cluster link density, lower inter-cluster link densityNote
Classic definitions of community-like structures are based on cohesion and on the interplay of cohesion and separation.
There is no unique definition of a network community but the following is commonly adopted:
Popular community definition: A sub-network where number of internal links is larger than the number of external links
strong community: Is a sub-network such that each node has more neighbors in the sub-network than in the rest of the network (internal degree > external degree)Weak community: A sub-network such that the sum of the internal degrees of all nodes exceeds the sum of their external degrees.Partition’s are particular division of a network into communities where each node belongs to only ONE community.Common Properties
number of possible partitions for a given set of nodes N

The triangular array whose right-hand diagonal sequence consists of Bell numbers


reality communities overlap (i.e. they share some of their nodes)(family, friends, work colleagues, etc)Cover: Division of a network into overlapping communities

An important metric for evaluating the quality of a community detection algorithm.
Assume that we have defined a particular partition of the network into communities.
internal degree the number of neighbors inside the community (number of black links)external degree the number of neighbors outside the community (number of blue links)community degree is the sum of the degrees of the nodes in the community;internal link density is the ratio between the number of internal links and the maximum number of links that could exist between any two community nodes. (i.e. Isolate internal sub-network and compute density as usual)\[ Q=\frac{1}{L} \sum_C\left(L_C-\frac{k_C^2}{4 L}\right) \]
Modularity can take negative values. e.g. A partition with \(N\) singletons:\[ Q_d=\frac{1}{L} \sum_C\left(L_C-\frac{k_C^{\text {in }} k_C^{o u t}}{L}\right), \]
NetworkX: returns the modularity of the input partition
modularity = nx.community.quality.modularity(G, partition)
large modularitynon-trivial maximum: \(0<Q_{\max }<1\)


Lets start simple with a binary partition
Graph bisection (minimum cut problem): binary partition case, network division into two clusters with equal number of nodes
General idea:
Initial Partition: Begin with an arbitrary split of the network into two clusters \(A\) and \(B\), often by randomly dividing the nodes.
Iterative Refinement (Kernighan–Lin Algorithm):
Termination Condition: The algorithm stops when successive iterations yield the same cut size—i.e., no further improvement is possible.
Generalization: The method can be extended beyond two clusters by considering node swaps between all cluster pairs.
Girvan-Newman algorithmLouvain methodLabel propagationIdentifying communities in networks is an unsupervised task known by various terms, including community detection, community discovery, and clustering.
separation NOT cohesion, not always ideal for community defection Network Partitioning: A general graph division problem focused on splitting the graph into parts—often of similar size—while minimizing edge cuts between them. Typically used for load balancing in parallel computing.
Community Detection: Aims to uncover natural, densely connected groups of nodes with more internal edges than external ones. No constraint on group size; emphasizes structural cohesion, not balance.
Key Difference: Partitioning prioritizes balanced size and minimal cuts; community detection focuses on revealing meaningful modular structure.
Modularity: Measures how densely connected nodes are within communities vs. a random baseline; higher is better. Used to evaluate splits in divisive methods.
Edge Betweenness: Identifies edges likely connecting communities (high betweenness); guides removal in divisive algorithms like Girvan–Newman.
Linkage Criteria (Agglomerative): Merge clusters based on metrics like edge weights, average distances, or edge density.
Conductance / Normalized Cut: Measures how well a cluster is separated from the rest of the graph; lower values mean tighter clusters.
Stability: Assesses robustness of communities over perturbations or time; useful for choosing dendrogram levels.
Summary:
Purpose: Fast, scalable algorithm for community detection in large networks.
Key Idea: Nodes iteratively adopt the most frequent label among their neighbors.
Initialization:
Iteration Process:
Convergence:
Advantages:
Limitations:
A Bridge removal algorithm


Strict definition: A bridge is a link whose removal breaks a connected network into two parts.Loose definition: Bridge is any link joining two communitiesThe Louvain algorithm is a popular modularity optimization method
Purpose: The Louvain algorithm is designed for detecting communities in large networks efficiently.
Methodology: It uses a two-phase iterative optimization process:
Repeat Process: These steps are repeated iteratively until modularity is maximized and cannot be increased further.
Performance: Known for its speed and scalability, making it suitable for very large networks. `* One benefit is that it is FAST!! can be used to detect communities in large networks with many millions of nodes and links.
Spectral clustering can be used for multiple clusters—it is not limited to graph bisection.
Graph Bisection: Using the Fiedler vector (second-smallest eigenvector of the Laplacian) partitions the graph into two parts. This is the classic spectral bisection method.
Multiple Clusters (k-way clustering): Spectral clustering generalizes naturally:
Why this works: The eigenvectors provide a low-dimensional embedding that preserves the graph’s community structure. Nodes in the same true cluster tend to be close together in this embedding.
Conclusion: Spectral clustering is a powerful, flexible method for detecting two or more clusters, especially in complex, non-convex, or graph-structured data.