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.

Improve this question
$\endgroup$
7
  • $\begingroup$ stackoverflow.com/q/64321080/781723 $\endgroup$
    – D.W. ♦
    Oct 13, 2020 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, 2020 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$
    – Ameet Rahane
    Oct 14, 2020 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$
    – Ameet Rahane
    Oct 14, 2020 at 3:05
  • 1
    $\begingroup$ A useful tag/keyword may be clustering. $\endgroup$
    – greybeard
    Oct 23, 2020 at 8:44

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

Your Answer

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

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