Graph Theory
When data is a set of relationships rather than a table, the questions become how nodes connect, which nodes matter, and which groups form. The page walks the graph topics first, from general libraries through connectivity, community detection, and node2vec embeddings to how communities are evaluated, then the Neo4j centrality, community, and experimental algorithms, and ends with graph and GNN courses and the Python tools to run it all.
The same notes are in Block Modeling - Distance Matrices, Deep walk, Fraud Detection, GRAPH NEURAL NETWORKS (GNN), Root Cause Effects (RCE/RCA), and Social Network Analysis.
Graph Topics
The general-purpose starting point is a single library that covers many unsupervised graph methods at once. General purpose and community detection GIT is Karate Club, an API oriented open-source Python framework for unsupervised learning on graphs (CIKM 2020).
Connectivity is the first structural question: where does the graph come apart? Min-cut: 1 implements the Karger min cut algorithm on a graph read from a text file. 2 is the Karger min cut from a repository of algorithms learned in Stanford's Algorithms: Design and Analysis. Min cut 3 is another Karger min cut algorithm implementation in Python.
Cutting a graph leads directly to finding its communities. Louvain community is taynaud/python-louvain, Louvain community detection. Girvan–Newman gist is community detection with the Girvan-Newman algorithm, which several repositories implement as divisive hierarchical clustering: this worked is ZwEin27/Community-Detection, and this is potentially good too is riteshkasat/Community-Detection-Algorithm. The remaining implementations are another, the Girvan-Newman clustering used by the Service Cutter; another, the same ZwEin27 repository again; and another, kjahan's Python implementation of the Girvan-Newman algorithm.
Communities describe groups; embeddings give each node a vector a model can use. Node2vec is the FIFA17 example notebook in eliorc's repository of code related to his Medium blog posts. The paper is node2vec: Scalable Feature Learning for Networks. medium1 is Think your Data Different, on applying deep learning to graph datasets in social networks, recommender systems, and biology, where data is inherently structured as a graph. medium 2 is node2vec: Embeddings for Graph Data, which argues that quality embeddings are the opposite of "garbage in, garbage out". The implementation of the node2vec algorithm — tutorial — is the code, and the git code is the same FIFA17 notebook from the Medium posts. The original py2 code is aditya-grover/node2vec, and taboola code for their medium paper is the taboola/node2vec-example notebook.
The same notes are in Node2vec.
Once communities are found, they have to be judged. Evaluation metrics for community detection is the Stack Overflow question on evaluation metrics for community detection algorithms. Review for community detection algorithms is Community detection in graphs, and the same review's abstract page is the paper: community structure, or clustering, is the organization of vertices in clusters with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Term: community structure is the Wikipedia entry on community structure and its algorithms for finding communities, and [Term: modularity of networks](https://en.wikipedia.org/wiki/Modularity_(networks) is the Wikipedia entry on modularity (networks).
Two papers are still on the reading pile. Unread paper is the first. Unread comparison of community detection algos compares community detection algorithms for multiplex graphs, where a multiplex is a set of graphs on the same vertex set, i.e. a generalized graph for multiple relationships with parallel edges between vertices.
Community detection can also be treated as clustering a matrix. Clustering adjacency matrices is Fahd's Cross Validated question on the best way for clustering an adjacency matrix, built from partial correlations of neural time series. Spectral-clustering is Spectral Clustering: A quick overview, from calculated | content. Finding natural groups in undirected graphs is the question on finding natural groups or clusters in one undirected graph or over several graphs that may share nodes. For more, Awesome community detection on github is a curated list of community detection research papers with implementations.
The ready-made versions of these algorithms are in the Neo4j Graph Data Science library, and Various algorithms is its manual; the subsections below follow its chapters.
Centrality algorithms
Centrality answers which nodes matter most, and 5. Centrality algorithms is the Neo4j chapter with explanations and examples for each centrality algorithm in the library:
Community detection algorithms
After the important nodes come the groups, and 6. Community detection algorithms is the chapter with explanations and examples for each community detection algorithm in the library, including Louvain from the topics above:
Experimental algorithms
Beyond the stable chapters, 7. Experimental algorithms extends the same manual to procedures, path finding, similarity, and link prediction:
Graph/GNN courses
The algorithms above are classical; the courses carry the same graphs into machine learning and graph neural networks.
The same notes are in GNN courses.
Machine learning with graphs by Stanford is CS224W. Graph deep learning course is the geometric deep learning course on grids, groups, graphs, geodesics, and gauges. Its keynote version is Michael Bronstein's ICLR 2021 talk "Geometric Deep Learning: The Erlangen Programme of ML" — graphs, sets, groups, GNNs — on YouTube.
Graph Tools
To run any of this in Python, two libraries do the graph handling. Graph-tool is an efficient Python module for manipulation and statistical analysis of graphs. NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.
Last updated
Was this helpful?