CODEWITHSUNDEEP
pythoncluster-analysisgraph-tool
Enrique Castaneda
Enrique Castaneda

Reputation: 145

Model for generating and detecting communities in dense network

I have a complete undirected weighted graph. Think of a graph where persons are nodes and the edge (u,v,w) indicates the kind of relationship between u and v with weight w. w can take any value between 1 (doesn't know each other - hence the completeness), 2 (acquaintances), 3(friends). This kind of relationships form naturally clusters based on the edge weight.

My goal is to define a model that models this phenomena and from where I can sample some graphs and see the observed behaviour in reality.

So far I've played with stochastic block models (https://graspy.neurodata.io/tutorials/simulations/sbm.html) since there are some papers about the use of these generative models for these community-detection tasks. However I may be overseeing something, since I can't seem to be able to fully represent what I need: g = sbm(list_of_params) where g is complete and there are some discernibles clusters among nodes sharing weight 3.

At this point I am not even sure whether sbm is the best approach for this task.

I am also assuming that everything that graph-tool can do, graspy can also do. Since at the beginning I read about both and it seems that is the case.

Summarizing:

  1. Is there a way to generate a stochastic block model in graspy that yields a complete undirected weighted graph?

  2. Is sbm the best model for the task. Should I be looking at gmm?

Thanks

Upvotes: 0

Views: 255

Answers (1)

Stuart Berg
Stuart Berg

Reputation: 18182

Is there a way to generate a stochastic block model in graspy that yields a complete undirected weighted graph?

Yes, but as pointed out in the comments above, that's a strange way to specify the model. If you want to benefit from the deep literature on community detection in social networks, you should not use a complete graph. Do what everyone else does: The presence (or absence) of an edge should indicate a relationship (or lack thereof), and an optional weight on the edge can indicate the strength of the relationship.

To generate graphs from SBM with weights, use this function: https://graspy.neurodata.io/reference/simulations.html#graspologic.simulations.sbm

I am also assuming that everything that graph-tool can do, graspy can also do.

This is not true. There are (at least) two different popular methods for inferring the parameters of an SBM. Unfortunately, the practitioners of each method seem to avoid citing each other in their papers and code.

  • graph-tool uses an MCMC statistical inference approach to find the optimal graph partitioning.
  • graspologic (formerly graspy) uses a trick related to spectral clustering to find the partitioning.

From what I can tell, the graph-tool approach offers more straightforward and principled model selection methods. It also has useful extensions, such as overlapping communities, nested (hierarchical) communities, layered graphs, and more.

I'm not as familiar with the graspologic (spectral) methods, but -- to me -- they seem more difficult to extend beyond merely seeking a point estimate for the ideal community partitioning. You should take my opinion with a hefty bit of skepticism, though. I'm not really an expert in this space.

Upvotes: 1

Related Questions