0
$\begingroup$

I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a weight given by a weight matrix.

My goal is to visualize subnetworks (areas where points close to each other also have a dense set of edge weights) where the subnetwork is colored by the given weight. However, this is extremely computationally expensive, as there are 9M edges. I'm looking for an algorithm that can either return the subnetworks, visualize these subnetworks, or something similar.

$\endgroup$
7
  • $\begingroup$ stackoverflow.com/q/64321080/781723 $\endgroup$
    – D.W.
    Oct 13 '20 at 22:18
  • $\begingroup$ I don't understand the task. What is meant by "colored by the given weight"? What are the inputs to the algorithm? Why can't you just extract the subnetwork, treat that as a new graph, and plot it with any graph visualization tool? $\endgroup$
    – D.W.
    Oct 13 '20 at 22:27
  • $\begingroup$ @D.W. How would I extract the subnetwork? The problem with most graph viz libraries is they don't allow for viz in euclidean space (nodes represent poitns in R^3). The inputs to the algorithm would be a set of weights and a set of vertices - you could think of this as a directed weighted graph, perhaps. How, would I then return a subnetwork of points that fall in a euclidean cluster and have high weights. $\endgroup$ Oct 14 '20 at 3:03
  • $\begingroup$ @D.W. why did you point to my stackoverflow post with the same question? They were the ones that told me to come here $\endgroup$ Oct 14 '20 at 3:05
  • 1
    $\begingroup$ A useful tag/keyword may be clustering. $\endgroup$
    – greybeard
    Oct 23 '20 at 8:44
1
$\begingroup$

It sounds like you don't need to be talking about this as a "graph" data structure.. you have points in R3 and you want to partition them into clusters based on their distances (or their pairwise weight matrix). This is more a statistical clustering problem than a graph clustering problem.

Here are some python functions to accomplish these: https://scikit-learn.org/stable/modules/clustering.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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