2
$\begingroup$

I have been reading about Clustering Models on Graph/Network data.

For example, there seems to be a popular Clustering Model for Graph/Network data called Louvain Clustering (https://en.wikipedia.org/wiki/Louvain_method). This model attempts to find "highly correlated subgraphs within the network" - this is also called "Community Detection" (it seems like the terms "clusters", "communities" are interchangeable here).

I was looking at the steps involved in Louvain Clustering:

enter image description here

As seen in the above description, clusters are identified through the Louvain Method by only using "edge" information.

For example, suppose that we have network data on a group of friends - we can break this data into two general parts:

Node Data: In this example, each person can be considered as a "Node". Thus, "Node Data" can be considered as Age, Salary, Height, Weight, etc. In a certain sense, this "Node Information" is analogous to "Covariate Information" in regression problems (e.g. the height of an individual person (node) in graph network vs. the height of an individual person in a regression dataset).

Edge Data: In this example, the relationships between friends can be considered as "Edges". For instance, if John and Jack are friends - their friendship can be considered as an "Edge".

It seems that most Graph Clustering Models (e.g. Louvain, Leiden, Walktrap, Infomap) only use "Edge Information" and do not make use of "Node Information" at all.

We can see an example of this in R:

#load libraries and data
library(igraph)
library(igraphdata)

data("karate")
#plot(karate)

#run clustering algorithm

set.seed(123)
gD = karate
lou <- cluster_louvain(gD)
LO = layout_with_fr(gD)
plot(lou, gD, vertex.label = NA, vertex.size=5, 
    edge.arrow.size = .2, layout=LO)

enter image description here

In the above code, we see how clustering was performed in the complete absence of "Node Information" - clustering was performed only using "Edge Information".

This is in stark contrast to standard clustering methods such as "K-Means Clustering". For example, if we were to use K-Means Clustering on a data set such as the Iris Flowers Dataset, K-Means would make use of the covariate information such as the different lengths and widths of the flowers.

The reason I am bringing this up : In the case of Graph/Network Clustering, it seems likely that there could be valuable information within the "Node Data" (also called "Node Attributes") - but most Graph/Network Clustering Models seem unable to exploit this information.

My Question: Are there any Graph/Network Clustering Models that are able to make use of both "Node Information" and "Edge Information" at the same time?

Thanks!

$\endgroup$

1 Answer 1

4
$\begingroup$

There are many methods proposed to detect communities in attributed networks. The three main approaches are: 1) combining structure- and attribute-based information in a single representation (e.g. by adding to the graph some vertices representing attributes), then detecting communities based on this representation; 2) detecting communities by considering simultaneously structure and attributes (e.g. by jointly optimizing two criteria); and 3) detecting communities separately using structure and attributes, then combining the resulting partitions (akin to consensus-based clustering methods).

To get a more precise overview of the existing methods, you should look for recent surveys such as (Chunaev'20). I did not find any implementation of these methods integrated in any of the major network libraries such as igraph or networkx. However, some authors have published their source code online, so you can look for a suitable method in the above review and check whether its source code is available in the original publication. For instance, I-Louvain, an attribute-based variant of Louvain described in (Combe'15), is available online: https://www.dropbox.com/sh/j4aqitujiaifgq4/AAAAH0L3uIPYNWKoLpcAh0TPa.

$\endgroup$
2
  • $\begingroup$ Thank you so much! I will look into this! $\endgroup$
    – stats_noob
    Apr 9, 2022 at 22:36
  • $\begingroup$ +1 I have gotten a lot of value out of networkx. Note that if you cluster the nodes, you can represent the clusters nicely by drawing them as hyperedges using hypernetx. $\endgroup$
    – Galen
    Apr 25, 2022 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.