Weighted directed graph clustering

user_4866010 0
Viewed 95

I'm generating graphs which look something like this and has the following properties:

  • edges are weighted and directed
  • nodes are either blue or red
  • blue nodes only connect to blue nodes
  • red nodes only connect to blue nodes

Which would be the best way of clustering the blue nodes into the strongly connected components I see? The higher weight edges are represented by thicker arrows.

I'm using NetworkX and PyVis. I have looked at the community detection algorithms available here but I have no idea where to start, there's just too many.

Example graph

enter image description here

GraphML for the image

<?xml version='1.0' encoding='utf-8'?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd"><key id="d3" for="edge" attr.name="weight" attr.type="double"/>
<key id="d2" for="node" attr.name="type" attr.type="string"/>
<key id="d1" for="node" attr.name="title" attr.type="string"/>
<key id="d0" for="node" attr.name="color" attr.type="string"/>
<graph edgedefault="directed"><node id="e_59">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_51">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_34">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_49">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_7">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_143">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_109">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_154">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_155">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_127">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_254">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_185">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_183">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_214">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="e_221">
  <data key="d0">blue</data>
  <data key="d1"></data>
  <data key="d2">excitatory</data>
</node>
<node id="i_62">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_1">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_27">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_40">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_48">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_52">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_14">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_10">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_55">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_19">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_36">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_2">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_44">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_53">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<node id="i_3">
  <data key="d0">red</data>
  <data key="d1"></data>
  <data key="d2">inhibitory</data>
</node>
<edge source="e_59" target="e_34">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_51" target="e_34">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_51" target="e_49">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_34" target="e_49">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_49" target="e_7">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_49" target="e_51">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_49" target="e_59">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_143" target="e_154">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_109" target="e_143">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_154" target="e_127">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_155" target="e_109">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_127" target="e_143">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_127" target="e_154">
  <data key="d3">0.0075</data>
</edge>
<edge source="e_254" target="e_183">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_254" target="e_221">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_185" target="e_183">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_185" target="e_254">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_183" target="e_185">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_183" target="e_214">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_183" target="e_221">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_214" target="e_185">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_214" target="e_221">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_214" target="e_254">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_221" target="e_185">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_221" target="e_214">
  <data key="d3">0.0005</data>
</edge>
<edge source="e_221" target="e_254">
  <data key="d3">0.0005</data>
</edge>
<edge source="i_62" target="e_34">
  <data key="d3">0.001</data>
</edge>
<edge source="i_62" target="e_49">
  <data key="d3">0.001</data>
</edge>
<edge source="i_62" target="e_155">
  <data key="d3">0.001</data>
</edge>
<edge source="i_62" target="e_185">
  <data key="d3">0.001</data>
</edge>
<edge source="i_1" target="e_127">
  <data key="d3">0.001</data>
</edge>
<edge source="i_1" target="e_183">
  <data key="d3">0.001</data>
</edge>
<edge source="i_1" target="e_214">
  <data key="d3">0.001</data>
</edge>
<edge source="i_27" target="e_34">
  <data key="d3">0.001</data>
</edge>
<edge source="i_27" target="e_59">
  <data key="d3">0.001</data>
</edge>
<edge source="i_27" target="e_154">
  <data key="d3">0.001</data>
</edge>
<edge source="i_27" target="e_183">
  <data key="d3">0.001</data>
</edge>
<edge source="i_27" target="e_185">
  <data key="d3">0.001</data>
</edge>
<edge source="i_27" target="e_214">
  <data key="d3">0.001</data>
</edge>
<edge source="i_40" target="e_49">
  <data key="d3">0.001</data>
</edge>
<edge source="i_40" target="e_154">
  <data key="d3">0.001</data>
</edge>
<edge source="i_48" target="e_49">
  <data key="d3">0.001</data>
</edge>
<edge source="i_48" target="e_59">
  <data key="d3">0.001</data>
</edge>
<edge source="i_48" target="e_109">
  <data key="d3">0.001</data>
</edge>
<edge source="i_48" target="e_155">
  <data key="d3">0.001</data>
</edge>
<edge source="i_48" target="e_183">
  <data key="d3">0.001</data>
</edge>
<edge source="i_48" target="e_214">
  <data key="d3">0.001</data>
</edge>
<edge source="i_52" target="e_51">
  <data key="d3">0.001</data>
</edge>
<edge source="i_52" target="e_109">
  <data key="d3">0.001</data>
</edge>
<edge source="i_52" target="e_185">
  <data key="d3">0.001</data>
</edge>
<edge source="i_14" target="e_109">
  <data key="d3">0.001</data>
</edge>
<edge source="i_14" target="e_127">
  <data key="d3">0.001</data>
</edge>
<edge source="i_14" target="e_155">
  <data key="d3">0.001</data>
</edge>
<edge source="i_14" target="e_183">
  <data key="d3">0.001</data>
</edge>
<edge source="i_14" target="e_214">
  <data key="d3">0.001</data>
</edge>
<edge source="i_10" target="e_49">
  <data key="d3">0.001</data>
</edge>
<edge source="i_10" target="e_59">
  <data key="d3">0.001</data>
</edge>
<edge source="i_10" target="e_221">
  <data key="d3">0.001</data>
</edge>
<edge source="i_55" target="e_49">
  <data key="d3">0.001</data>
</edge>
<edge source="i_55" target="e_155">
  <data key="d3">0.001</data>
</edge>
<edge source="i_55" target="e_183">
  <data key="d3">0.001</data>
</edge>
<edge source="i_55" target="e_254">
  <data key="d3">0.001</data>
</edge>
<edge source="i_19" target="e_7">
  <data key="d3">0.001</data>
</edge>
<edge source="i_19" target="e_34">
  <data key="d3">0.001</data>
</edge>
<edge source="i_19" target="e_49">
  <data key="d3">0.001</data>
</edge>
<edge source="i_19" target="e_51">
  <data key="d3">0.001</data>
</edge>
<edge source="i_19" target="e_155">
  <data key="d3">0.001</data>
</edge>
<edge source="i_19" target="e_185">
  <data key="d3">0.001</data>
</edge>
<edge source="i_19" target="e_214">
  <data key="d3">0.001</data>
</edge>
<edge source="i_36" target="e_7">
  <data key="d3">0.001</data>
</edge>
<edge source="i_36" target="e_127">
  <data key="d3">0.001</data>
</edge>
<edge source="i_36" target="e_155">
  <data key="d3">0.001</data>
</edge>
<edge source="i_36" target="e_214">
  <data key="d3">0.001</data>
</edge>
<edge source="i_2" target="e_7">
  <data key="d3">0.001</data>
</edge>
<edge source="i_2" target="e_51">
  <data key="d3">0.001</data>
</edge>
<edge source="i_2" target="e_59">
  <data key="d3">0.001</data>
</edge>
<edge source="i_2" target="e_154">
  <data key="d3">0.001</data>
</edge>
<edge source="i_2" target="e_185">
  <data key="d3">0.001</data>
</edge>
<edge source="i_44" target="e_34">
  <data key="d3">0.001</data>
</edge>
<edge source="i_44" target="e_49">
  <data key="d3">0.001</data>
</edge>
<edge source="i_44" target="e_59">
  <data key="d3">0.001</data>
</edge>
<edge source="i_44" target="e_154">
  <data key="d3">0.001</data>
</edge>
<edge source="i_53" target="e_34">
  <data key="d3">0.001</data>
</edge>
<edge source="i_53" target="e_49">
  <data key="d3">0.001</data>
</edge>
<edge source="i_53" target="e_109">
  <data key="d3">0.001</data>
</edge>
<edge source="i_53" target="e_127">
  <data key="d3">0.001</data>
</edge>
<edge source="i_53" target="e_183">
  <data key="d3">0.001</data>
</edge>
<edge source="i_3" target="e_51">
  <data key="d3">0.001</data>
</edge>
<edge source="i_3" target="e_143">
  <data key="d3">0.001</data>
</edge>
<edge source="i_3" target="e_154">
  <data key="d3">0.001</data>
</edge>
<edge source="i_3" target="e_254">
  <data key="d3">0.001</data>
</edge>
</graph></graphml>
networkx cluster-analysis
0 Answers
Related