Source-linked AI summary
Batch kernel SOM and related Laplacian methods for social network analysis
Romain Boulet, Bertrand Jouve, Fabrice Rossi, Nathalie Villa
TL;DR
Large graphs pose a challenge for summarizing communities and their relationships, while perfect-community methods can cover only part of a graph. The paper combines Laplacian-based community analysis with a batch kernel SOM, and reports that both approaches provide useful but distinct perspectives for historians studying a medieval social network.
Problem
Large-network analysis seeks communities and their relationships, but perfect communities can cover only part of a real graph and there is no consensus on a formal community definition.
Source: §1 · p. 2, §2 · pp. 3–4Method
The paper combines Laplacian-based perfect-community analysis with a batch kernel SOM using a Laplacian-derived kernel to map vertices and their relationships.
Source: §1 · p. 3, §4.5 · p. 15Results
Both approaches provide elements for historians to understand medieval society’s organization, but have distinct advantages and weaknesses.
Source: §5.7 · p. 28Takeaways & Limitations
The kernel SOM organizes all graph vertices, complementing the perfect-community view, which covers only a subset.
Source: §2 · p. 4, §5.7 · p. 28Perfect communities cover only part of real graphs and can miss relevant groupings; in the studied network, only 35% of vertices belong to one.
Source: §3 · p. 7
Abstract
from arXiv · showhide
Large graphs are natural mathematical models for describing the structure of the data in a wide variety of fields, such as web mining, social networks, information retrieval, biological networks, etc. For all these applications, automatic tools are required to get a synthetic view of the graph and to reach a good understanding of the underlying problem. In particular, discovering groups of tightly connected vertices and understanding the relations between those groups is very important in practice. This paper shows how a kernel version of the batch Self Organizing Map can be used to achieve these goals via kernels derived from the Laplacian matrix of the graph, especially when it is used in conjunction with more classical methods based on the spectral analysis of the graph. The proposed method is used to explore the structure of a medieval social network modeled through a weighted graph that has been directly built from a large corpus of agrarian contracts.
1 Introduction
The paper addresses how to summarize large networks by finding communities and representing their relationships. It combines Laplacian-based analysis with a batch kernel SOM to offer complementary community views and a two-dimensional organization map.
1 Introduction
- Finding tightly connected groups and understanding relations among them are central challenges in making large, structurally complex networks easier to understand.The introduction notes that analysis of very large graphs, including those with millions of vertices, remains an open question.Source: §1 · p. 2
- The paper combines a classical Laplacian-based approach with a batch kernel SOM to identify and map complementary kinds of communities.The spectral approach extracts a specific community type but covers only part of the studied graph; the SOM maps vertices into less formal communities whose links require careful interpretation.Source: §1 · pp. 2–3
- Both approaches associate community organization with a two-dimensional representation that sketches relations among small homogeneous groups rather than drawing the whole graph.The paper applies the methods to a medieval social network modeled from agrarian contracts and compares the results with prior historical knowledge.Source: §1 · p. 3
2 Clustering through the search of perfect communities
This section defines perfect communities as a restrictive, structurally precise community type and describes how Laplacian eigenvectors can identify them. Their simple representations preserve internal and external links, but they cover only part of many real graphs, motivating additional structural elements in a graph summary.
2 Clustering through the search of perfect communities
- A perfect community is a complete subgraph of at least two vertices whose members have exactly the same neighbors outside it.For a weighted graph, the paper defines perfect communities using the corresponding unweighted graph with the same vertices and edges.Source: §2 · p. 4
- A glyph for each perfect community can preserve its internal completeness and shared external connections without losing link information.Each glyph represents a complete subgraph, and a single link between glyphs represents the common external connections of its member vertices.Source: §2 · p. 4
- Perfect communities may cover only part of a real graph, leaving out important vertices and producing many very small communities.The section also notes that omitted vertices can be central to the network’s structure.Source: §2 · p. 4
- High-degree vertices may form a dense, small-diameter rich-club, while high-betweenness vertices can connect otherwise separate subgroups.The paper selects central vertices by examining how adding vertices in decreasing betweenness order reduces the number of connected components, balancing coverage against visual clutter.Source: §2 · pp. 4–5
- The representation can add central vertices and a rich-club to perfect communities, but its rich-club glyph suppresses that group’s internal structure.An edge to the rich-club may summarize a complex set of links.Source: §2 · p. 5
- For a non-stable vertex set S, perfect-community status is equivalent to a nonzero Laplacian eigenvalue of multiplicity at least k−1, whose k−1 associated eigenvectors vanish on the same n−k coordinates.The set has k vertices; coordinates where those eigenvectors are nonzero represent its vertices, and λ = d + 1, where d is the degree of a vertex in S.Source: §2 · p. 6
3 Similarity measures built from the Laplacian
This section presents Laplacian-derived similarities and kernels as complementary ways to cluster graph vertices. It relates spectral clustering to perfect communities and introduces the diffusion kernel, which uses the Laplacian spectrum to map vertices into a feature space.
3 Similarity measures built from the Laplacian
- Because perfect communities can omit many vertices and groupings, the section turns to Laplacian-derived similarities and kernels as complementary clustering tools.The studied social network has only 35% of its vertices in perfect communities.Source: §3 · p. 7
3.1 From almost perfect communities to graph cuts
- Graph-cut clustering seeks a partition that minimizes a cut-quality measure, then relaxes the discrete search to a real-valued problem.For p > 2, the stated optimization is NP-complete; the relaxed solution uses the p eigenvectors associated with the smallest positive Laplacian eigenvalues.Source: §3.1 · pp. 7–8
- Spectral clustering maps vertices using those eigenvectors and applies a standard clustering algorithm, such as k-means, to their mapped coordinates.It is related to perfect-community search because vertices in the same perfect community share coordinates for many eigenvectors.Source: §3.1 · p. 8
- The described spectral-clustering variant weights its first p eigenvectors equally and uses only that portion of the Laplacian spectrum.The section motivates regularization because smaller eigenvalues indicate more important eigenvectors and the truncated approach omits other spectral information.Source: §3.1 · p. 8
3.2 Diffusion kernel
- The diffusion kernel is derived by applying a regularization function to the Laplacian; its diffusion matrix is Dβ = e^−βL.The paper describes the kernel as inducing a feature-space mapping and relates it to diffusion of energy along graph edges.Source: §3.2 · pp. 8–9
- The parameter β controls smoothing: small values prevent clustering nonadjacent vertices, while large values allow grouping vertices with many common neighbors.Unlike the truncated spectral mapping, the diffusion kernel uses the whole eigendecomposition with a modified metric containing nonlocal information.Source: §3.2 · p. 10
4 Kernel SOM for clustering the vertices of a graph
The section motivates a SOM to cluster vertices while preserving relationships among clusters, then develops a Laplacian-kernel batch SOM for graph nodes. It explains the implementation choices and the criteria used to compare maps.
4.1 Motivations for the use of the SOM algorithm
- A SOM offers imperfect communities arranged to reflect inter-community relationships, addressing the limited coverage of perfect communities and the complex links between ordinary clusters.The SOM combines clustering with nonlinear projection, placing close clusters near one another in its prior structure.Source: §4.1 · p. 10
4.2 SOM for non vector data
- The standard SOM cannot directly handle graph vertices, so the paper uses a kernel SOM with a diffusion kernel to cluster and project them while respecting feature-space topology.The authors note that other kernels, dissimilarity SOMs, or embeddings may work better in other applications; this article explores one implementation.Source: §4.2 · pp. 11–12
- For the studied network, a standard SOM on an explicit spectral embedding produced highly unbalanced clusters, including one containing two thirds of the vertices.The paper contrasts this with the kernel approach, whose heat kernel helps distinguish vertices that may appear similar using only the smallest Laplacian eigenvectors.Source: §4.2 · p. 12
4.3 Batch kernel SOM
- The batch kernel SOM applies batch SOM in an implicit feature space, using kernel inner products instead of explicitly constructing the feature map.Its neurons have prototypes represented as linear combinations of mapped observations, and the algorithm alternates assignment and prototype-update steps.Source: §4.3 · pp. 12–13
4.4 Implementation details
- Initialization matters: kernel-PCA initialization with an optimal initial temperature performed much better than random initialization in the map-selection tests.The implementation also uses a square grid, Gaussian neighborhoods, and geometrically decreasing temperature; annealing ends with local organization behavior.Source: §4.4 · pp. 14–15
4.5 Comparing Maps
- Quantization error alone cannot assess topology preservation and decreases as cluster count grows; q-modularity offers a clustering-only comparison across choices such as β.A high q-modularity indicates dense within-cluster connections and few edges between clusters.Source: §4.5 · pp. 15–16
- The Kaski–Lagus measure combines quantization error with continuity, balancing fit against whether nearby feature-space vertices map to nearby units.The continuity term supports comparing map sizes, though the criterion is likely to favor larger maps.Source: §4.5 · pp. 15–16
5 Mining a medieval social network
The section applies perfect-community analysis and a batch kernel SOM to a peasant network built from medieval agrarian contracts. Together, the methods map tightly defined groups and broader vertex clusters, revealing complementary views of the network’s social and historical organization.
5.2 First description of the graph
- The graph contains 615 vertices and 4,193 edges, built from about 1,000 contracts that record peasants and their social relations.The analyzed graph is its largest connected component; nobles and notaries are removed, and links are weighted by qualifying contracts.Source: §5.1 · p. 16, §5.2 · pp. 17–18
5.3 Clustering the medieval graph into perfect communities and rich-club
- The analysis finds 76 perfect communities, mostly groups of two or three people, and a rich club of 19 vertices.The perfect-community representation covers 35% of the graph; linked communities and central individuals form part of its mapped structure.Source: §5.3 · pp. 18–20
5.4 Mapping the medieval graph with the SOM
- The selected 7 × 7 SOM has 35 nonempty clusters, including a largest cluster of 255 vertices connected to two other dense parts.The largest cluster was mapped again with a second 7 × 7 SOM; its largest cluster contains 81 vertices.Source: §5.4 · pp. 22–24
5.5 Historical properties of the self-organizing map
- SOM clusters show historical structure: the top-right is oldest, the bottom-right has middle dates, and the top-left is most recent.The earlier part connects to the rest through only 1 to 3 individuals; cluster locations are generally geographically homogeneous, while family names usually are not.Source: §5.5 · pp. 24–25
5.6 Comparison with the work on perfect communities
- Perfect communities and the SOM show strong agreement on linked groups, while the SOM places some linked communities nearby and maps the whole graph.The authors conclude that the approaches have distinct advantages and weaknesses: perfect communities support local interpretation, while the SOM gives a broader view.Source: §5.6 · pp. 25, 27, §5.7 · p. 28
- The SOM separates the rich club into three nearby clusters, but the authors say whether that separation is meaningful remains unclear.The rich-club approach highlights members’ special social role, whereas the corresponding SOM clusters have no similarly specific feature.Source: §5.6 · p. 27
5.7 Conclusion
- The methods facilitate historical analysis rather than automate it, and SOM map size and hierarchical depth remain open parameter choices.The authors suggest using perfect communities to help judge the relevance of a SOM cluster.Source: §5.7 · pp. 28–29