AI News, Graph-based machine learning: Part 2
Graph-based machine learning: Part 2
In my previous post, we discussed the foundation of community detection using modularity optimization.
Two great properties emerge from this approach These are important points to highlight as they make distributed computation a prime candidate for this memory problem.
The best way to do this at scale (when you don’t know where the information ultimately is on disk) is by using distributed transactions (aka passing messages).
In the context of community detection, each node sends a message to its neighbors with content along the lines of: “Hey I’m your friendly neighbor Node 3 from Community 12” If you’ve ever worked with graphs you’re likely to be very familiar with the concepts of vertices and edges.
Independently, and in parallel, each node waits for its turn to reduce all its messages into a coherent local sum of weighted edges, and make a decision based on the local modularity deltaQ of each neighboring community.
This is done by creating a new graph with a new set of nodes (corresponding to each community) and edges being inferred from the edges during the previous computation (e.g.
Note that additional information, say the internal coherence within a community, can be propagated in a similar fashion to the condensed node and provide valuable information.
Finally, here we have a fully functional procedure to perform modularity optimization on graphs of ridiculously large size, assuming we have enough computers to store all the information on disk.
The intermediary step should therefore be saved for further investigation as they likely yield valuable information on the structural complexity of the data.
This change of scales, previously limited by RAM, opens exciting perspectives as the self modular structure of complex systems have been shown to hold crucial information to understanding their nature.
Being an unsupervised learning technique and an initial starting point for a lot of analysis, the low barriers of entry make this approach applicable to a wide range of datasets.
It was designed to measure the strength of division of a network into modules (also called groups, clusters or communities).
Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules.
However, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities.
For example, biological and social patterns, the World Wide Web, metabolic networks, food webs, neural networks and pathological networks are real world problems that can be mathematically represented and topologically studied to reveal some unexpected structural features. Most of these networks possess a certain community structure that has substantial importance in building an understanding regarding the dynamics of the network.
For instance, a closely connected social community will imply a faster rate of transmission of information or rumor among them than a loosely connected community.
Thus, if a network is represented by a number of individual nodes connected by links which signify a certain degree of interaction between the nodes, communities are defined as groups of densely interconnected nodes that are only sparsely connected with the rest of the network.
Hence, it may be imperative to identify the communities in networks since the communities may have quite different properties such as node degree, clustering coefficient, betweenness, centrality. etc., from that of the average network.
Modularity is the fraction of the edges that fall within the given groups minus the expected fraction if edges were distributed at random.
. It is positive if the number of edges within groups exceeds the number expected on the basis of chance.
For a given division of the network's vertices into some modules, modularity reflects the concentration of edges within modules compared with random distribution of links between all nodes regardless of modules.
There are different methods for calculating modularity. In the most common version of the concept, the randomization of the edges is done so as to preserve the degree of each vertex.
(It is important to note that multiple edges may exist between two nodes, but here we assess the simplest case).
Modularity Q is then defined as the fraction of edges that fall within group 1 or 2, minus the expected number of edges within groups 1 and 2 for a random graph with the same node degree distribution as the given network.
The expected number of edges shall be computed using the concept of Configuration Models. The configuration model is a randomized realization of a particular network.
the configuration model cuts each edge into two halves, and then each half edge, called a stub, is rewired randomly with any other stub in the network even allowing self loops.
Thus, even though the node degree distribution of the graph remains intact, the configuration model results in a completely random network.
respectively and rewire the stubs for these two nodes, then, The total number of rewirings possible is equal to the number of stubs remaining after choosing a particular stub,
partitioning into two communities, then the two sub-communities further partitioned into two smaller sub communities only to maximize Q) is a possible approach to identify multiple communities in a network.
Additionally, (3) can be generalized for partitioning a network into c communities. where eij is the fraction of edges with one end vertices in community i and the other in community j: and ai is the fraction of ends of edges that are attached to vertices in community i: We consider an undirected network with 10 nodes and 12 edges and the following adjacency matrix.
An alternative formulation of the modularity, useful particularly in spectral optimization algorithms, is as follows. Define Svr to be 1 if vertex v belongs to group r and zero otherwise.
Then and hence where S is the (non-square) matrix having elements Svr and B is the so-called modularity matrix, which has elements All rows and columns of the modularity matrix sum to zero, which means that the modularity of an undivided network is also always zero.
For networks divided into just two communities, one can alternatively define sv = ±1 to indicate the community to which node v belongs, which then leads to where s is the column vector with elements sv. This function has the same form as the Hamiltonian of an Ising spin glass, a connection that has been exploited to create simple computer algorithms, for instance using simulated annealing, to maximize the modularity.
The general form of the modularity for arbitrary numbers of communities is equivalent to a Potts spin glass and similar algorithms can be developed for this case also. Modularity compares the number of edges inside a cluster with the expected number of edges that one would find in the cluster if the network were a random network with the same number of nodes and where each node keeps its degree, but edges are otherwise randomly attached.
This assumption is however unreasonable if the network is very large, as the horizon of a node includes a small part of the network, ignoring most of it.
Moreover, this implies that the expected number of edges between two groups of nodes decreases if the size of the network increases.
So, if a network is large enough, the expected number of edges between two groups of nodes in modularity's null model may be smaller than one.
If this happens, a single edge between the two clusters would be interpreted by modularity as a sign of a strong correlation between the two clusters, and optimizing modularity would lead to the merging of the two clusters, independently of the clusters' features.
So, even weakly interconnected complete graphs, which have the highest possible density of internal edges, and represent the best identifiable communities, would be merged by modularity optimization if the network were sufficiently large. For this reason, optimizing modularity in large networks would fail to resolve small communities, even when they are well defined.
This bias is inevitable for methods like modularity optimization, which rely on a global null model. There are two main approaches which try to solve the resolution limit within the modularity context: the addition of a resistance r to every node, in the form of a self-loop, which increases (r>0) or decreases (r<0) the aversion of nodes to form communities; or the addition of a parameter γ>0 in front of the null-case term in the definition of modularity, which controls the relative importance between internal links of the communities and the null model. Optimizing modularity for values of these parameters in their respective appropriate ranges, it is possible to recover the whole mesoscale of the network, from the macroscale in which all nodes belong to the same community, to the microscale in which every node forms its own community, hence the name multiresolution methods.
- On Wednesday, January 16, 2019
Lecture 24 — Community Detection in Graphs - Motivation | Stanford University
Copyright Disclaimer Under Section 107 of the Copyright Act 1976, allowance is made for "FAIR USE" for purposes such as criticism, comment, news reporting, ...
Example to illustrate the calculation of Edge Betweenness using BFS
Introduction to SNA. Lecture 5. Network communities.
Cohesive subgroups. Graph cliques. Network communities. Graph partitioning. Modularity. Edge Betweenness. Spectral partitioning. Modularity maximization.
Gephi Modularity Tutorial
A quick tutorial on how to use gephi's modularity feature to detect communities and color code them in graphs.
My PhD thesis in ICTEAM: Detecting Communities
In this short video, researcher Arnaud Browet gives an overview of his PhD thesis «Algorithms for community and role detection in networks», which was ...
Using Gephi to visualise and understand communities
Quick video to show how you can use Gephi (a free graph visualisation tool) to quickly visualise communities in a network and use some of the features in Gephi ...
Detecting Communities in a Network Using Girvan Newman Algorithm (Python Implementation)
Implementation using Networkx package of Python.
Math 5840 - Modularity and Hieracrchical Graphs
Dr. Debra Knisley, ETSU Department of Mathematics and Statistics MATH 5840 - Complex Networks and Systems ETSU Online Programs ...
Louvain Community Detection
A visualization of the "Louvain" community detection algorithm in action. The input graph is the result of the search "windows".
Network Analysis. Lecture 8. Network communitites
Cohesive subgroups. Graph cliques, k-plexes, k-cores. Network communities. Vertex similarity matrix. Similarity based clustering. Agglomerative clustering.