Hot questions for Using Neural networks in graph theory

Question:

I have edges of a network:

  var links = [
  {source: "A", target: "D", type: "high"},
  {source: "A", target: "K", type: "high"},
  {source: "B", target: "G", type: "high"},
  {source: "H", target: "B", type: "high"},
  {source: "C", target: "A", type: "low"},
  {source: "C", target: "L", type: "low"},
  {source: "E", target: "A", type: "low"},
  {source: "F", target: "B", type: "low"},
  {source: "F", target: "G", type: "low"},
  {source: "K", target: "J", type: "low"},
  {source: "F", target: "I", type: "low"},
  {source: "G", target: "H", type: "low"},
  {source: "E", target: "K", type: "high"},
  {source: "E", target: "G", type: "low"},
  {source: "E", target: "F", type: "high"},
  {source: "E", target: "M", type: "high"},
];

From which I compute the nodes:

var nodes = {};

links.forEach(function(link) {
  link.source = nodes[link.source] || (nodes[link.source] = {name: link.source});
  link.target = nodes[link.target] || (nodes[link.target] = {name: link.target});
});

Giving a network like this:

I want to change opacity of nodes and edges when connected. I have a function to grab all the links/edges:

var linkedByIndex = {};
    links.forEach(function(d) {
        linkedByIndex[d.source.index + "," + d.target.index] = 1;
    });

I can then use this function to check all edges that are connected and e.g. change opacity of all those connected to a node:

function isConnected(a, b) {
    return linkedByIndex[a.index + "," + b.index] || linkedByIndex[b.index + "," + a.index] || a.index == b.index;
}


function fade(opacity) {
        return function(d) {

            node.style("stroke-opacity", function(o) {
                thisOpacity = isConnected(d, o) ? 1 : opacity;
                this.setAttribute('fill-opacity', thisOpacity);
                return thisOpacity;
            }); 
      ....etc.

This is here as a live example.

What I would like to do however is to return those edges that are part of a triad.

Therefore in the above diagram, if "E" was hovered, the edges E-A, E-K, A-K, as well as E-G, E-F and F-G would be returned. If "H" was hovered over, then H-G, H-B and B-G would be returned.

My aim is to highlight the triads belonging to each node. Importantly, I do not want incomplete triads. i.e. if "C" is hovered over, then it wouldn't select C-A and C-L as the triad is not closed with A-L.


Answer:

Very cool question. Here's one way to solve it.

First, I built a map of each node and what other nodes are attached to it:

// build a map of every node
// and which are attached to it
// to it both for source and target
// because you don't care about direction
var linkMap = {};
links.forEach(function(d){
  if (!linkMap[d.source.index]){
    linkMap[d.source.index] = [];
  }
  if (linkMap[d.source.index].indexOf(d.target.index) === -1){
    linkMap[d.source.index].push(d.target.index);
  }
  if (!linkMap[d.target.index]){
    linkMap[d.target.index] = [];
  }
  if (linkMap[d.target.index].indexOf(d.source.index) === -1){
    linkMap[d.target.index].push(d.source.index);
  }
});

Then on mouseover, walk the path 3 levels deep looking for one's that return to the starting point:

function followLink(d){

  // only one link, it can't trace back
  if (linkMap[d].length < 2)
    return [];

  var rv = [];
  // trace every route 3 deep
  linkMap[d].forEach(function(i){
    linkMap[i].forEach(function(j){
      linkMap[j].forEach(function(k){
        var a = [i,j,k]; //<-- array of indexes of nodes in triad
        // if there is no repeats in walking
        // and it starts and ends at the same spot
        if (a.filter(function(item, pos) {
          return a.indexOf(item) == pos;
        }).length === 3 && d === a[2]){
          rv.push(a);
        }
      });
    });
  });
  return rv; //<-- array of arrays of triads indexes
}

Working code:

<!DOCTYPE html>
<meta charset="utf-8">
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script src="http://marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>

<style>
  .node circle {
    stroke-width: 2px;
  }
  
  .node text {
    font-family: sans-serif;
    text-anchor: middle;
    pointer-events: none;
    user-select: none;
    -webkit-user-select: none;
  }
  
  .link {
    stroke-width: 4px;
  }
  
  text {
    font: 18px sans-serif;
    pointer-events: none;
  }
  
  #end-arrow {
    fill: #88A;
  }
</style>

<body>


  <script>
    function bar() {
      console.log("click");
      force.stop();
      force.start();
    }



    var links = [{
      source: "A",
      target: "D",
      type: "high"
    }, {
      source: "A",
      target: "K",
      type: "high"
    }, {
      source: "B",
      target: "G",
      type: "high"
    }, {
      source: "H",
      target: "B",
      type: "high"
    }, {
      source: "C",
      target: "A",
      type: "low"
    }, {
      source: "C",
      target: "L",
      type: "low"
    }, {
      source: "E",
      target: "A",
      type: "low"
    }, {
      source: "F",
      target: "B",
      type: "low"
    }, {
      source: "F",
      target: "G",
      type: "low"
    }, {
      source: "K",
      target: "J",
      type: "low"
    }, {
      source: "F",
      target: "I",
      type: "low"
    }, {
      source: "G",
      target: "H",
      type: "low"
    }, {
      source: "E",
      target: "K",
      type: "high"
    }, {
      source: "E",
      target: "G",
      type: "low"
    }, {
      source: "E",
      target: "F",
      type: "high"
    }, {
      source: "E",
      target: "M",
      type: "high"
    }, ];

    var nodes = {};

    // Compute the distinct nodes from the links.
    links.forEach(function(link) {
      link.source = nodes[link.source] || (nodes[link.source] = {
        name: link.source
      });
      link.target = nodes[link.target] || (nodes[link.target] = {
        name: link.target
      });
    });

    var width = 960,
      height = 700;

    var force = d3.layout.force()
      .nodes(d3.values(nodes))
      .links(links)
      .size([width, height])
      .linkDistance(105)
      .charge(-775)
      .on("tick", tick)
      .start();



    force.on("start", function() {
      console.log("start");
    });
    force.on("end", function() {
      console.log("end");
    });

    R = 18



    var svg = d3.select("body").append("svg")
      .attr("width", width)
      .attr("height", height);

    // add defs-marker
    // add defs-markers
    svg.append('svg:defs').selectAll("marker")
      .data([{
        id: "end-arrow",
        opacity: 1
      }, {
        id: "end-arrow-fade",
        opacity: 0.075
      }])
      .enter().append('marker')
      .attr('id', function(d) {
        return d.id;
      })
      .attr('viewBox', '0 0 10 10')
      .attr('refX', 2 + R)
      .attr('refY', 5)
      .attr('markerWidth', 4)
      .attr('markerHeight', 4)
      .attr('orient', 'auto')
      .append('svg:path')
      .attr('d', 'M0,0 L0,10 L10,5 z')
      .style("opacity", function(d) {
        return d.opacity;
      });

    //phantom marker
    svg.append('svg:defs')
      .append('svg:marker')
      .attr('id', 'end-arrow-phantom')
      .attr('viewBox', '0 0 10 10')
      .attr('refX', 2 + R)
      .attr('refY', 5)
      .attr('markerWidth', 4)
      .attr('markerHeight', 4)
      .attr('orient', 'auto')
      .attr('fill', '#EEE')
      .append('svg:path')
      .attr('d', 'M0,0 L0,10 L10,5 z');


    var link = svg.selectAll(".link")
      .data(force.links())
      .enter()
      .append("line")
      .attr("class", "link")
      .attr("stroke", "#88A")
      .attr('marker-end', 'url(#end-arrow)');

    var node = svg.selectAll(".node")
      .data(force.nodes())
      .enter().append("g")
      .attr("class", "node")
      .call(force.drag);

    node.append("circle")
      .attr("r", R)
      .attr("stroke", '#777')
      .attr("fill", '#DDD')
      .on("mouseover", function(d) {
        var t = followLink(d.index);
        if (t.length){
          link.style('opacity', '0');
          node.style('opacity','0');
          for (var i = 0; i < t.length; i++){
            var a = t[i];
            for (var j = 0; j < a.length; j++){
              var stop = a[j];
              d3.select(node[0][stop]).style('opacity','1');
              var start;
              if (j === 0) start = d.index;
              else start = start = a[j-1];
              links.forEach(function(l,k){
                if (l.source.index === start &&
                    l.target.index === stop){
                      d3.select(link[0][k]).style('opacity','1');
                    }
              });
            }
          }
          
          
          followLink(d.index).forEach(function(i){
            i.forEach(function(j){
              d3.select(node[0][j]).style('opacity','1');
            });
          });
        }
      })
      .on("mouseout", function(){
        node.style('opacity','1');
        link.style('opacity','1');
      });

    node.append("text")
      .attr("x", 0)
      .attr("dy", ".35em")
      .text(function(d) {
        return d.name;
      });

    function tick() {
      link
        .attr("x1", function(d) {
          return d.source.x;
        })
        .attr("y1", function(d) {
          return d.source.y;
        })
        .attr("x2", function(d) {
          return d.target.x;
        })
        .attr("y2", function(d) {
          return d.target.y;
        });

      node
        .attr("transform", function(d) {
          return "translate(" + d.x + "," + d.y + ")";
        });
    }

    // build a map of every node
    // and which are attached to it
    // to it both for source and target
    // because you don't care about direction
    var linkMap = {};
    links.forEach(function(d){
      if (!linkMap[d.source.index]){
        linkMap[d.source.index] = [];
      }
      if (linkMap[d.source.index].indexOf(d.target.index) === -1){
        linkMap[d.source.index].push(d.target.index);
      }
      if (!linkMap[d.target.index]){
        linkMap[d.target.index] = [];
      }
      if (linkMap[d.target.index].indexOf(d.source.index) === -1){
        linkMap[d.target.index].push(d.source.index);
      }
    });
    
    function followLink(d){

      // only one link, it can't trace back
      if (linkMap[d].length < 2)
        return [];
        
      var rv = [];
      // trace every route 3 deep
      linkMap[d].forEach(function(i){
        linkMap[i].forEach(function(j){
          linkMap[j].forEach(function(k){
            var a = [i,j,k];
            // if there is not repeats
            // and it starts and ends at the same spot
            if (a.filter(function(item, pos) {
              return a.indexOf(item) == pos;
            }).length === 3 && d === a[2]){
              rv.push(a);
            }
          });
        });
      });
      return rv;
    }

  </script>

Question:

Let's say I'm using this affiliation matrix:

library(igraph)

A=c(1,1,0,0) 
B=c(1,0,1,0) 
C=c(1,0,1,0) 
D=c(0,1,0,1) 
E=c(0,0,1,1) 
aff=matrix(c(A,B,C,D,E),nrow=5,byrow=TRUE) 
dimnames(aff)=list(c("A","B","C","D","E"),c("Group1","Group2","Group3","Group4"))

Which looks like this:

##   Group1 Group2 Group3 Group4
## A      1      1      0      0
## B      1      0      1      0
## C      1      0      1      0
## D      0      1      0      1
## E      0      0      1      1

From which you can produce (using aff %*% t(aff)) the following adjacency matrix:

##   A B C D E
## A 2 1 1 1 0
## B 1 2 2 0 1
## C 1 2 2 0 1
## D 1 0 0 2 1
## E 0 1 1 1 2

The groups (e.g. Group1, Group2, etc.) are not preserved in the transformation to an adjacency matrix, thus when plotting:

m2=aff %*% t(aff)
g2=graph_from_adjacency_matrix(m2, "undirected", weighted=T, diag=F)
plot(g2, edge.width=E(g2)$weight)

There is no way to know what shared group connection exists between A and B, A and C, etc.

My question: Is there some way to preserve this grouping variable so that the plot could be made from the adjacency matrix while allowing the edges to be labelled as Group3 or Group1 like so?:

Note: I'm planning to use visNetwork, not igraph, but this question seems to stem from the data structure itself rather than the package used, so I've chosen this for simplicity's sake.


Answer:

m3 = get.edgelist(g2)
lbls = sapply(1:NROW(m3), function(i){
    toString(names(which(aff[m3[i, 1],] == 1 & aff[m3[i, 2],] == 1)))
})
plot(g2, edge.label = lbls)

Question:

By 'standard format' I mean where the input and output nodes are in their own separate lines, with all other hidden nodes between them in the image. As you can see below, my input nodes are nodes 0,1,and 2, my output node is 3, my hidden nodes are 4 and 5. This is the best looking network graph I can get. I'm trying to avoid using keras because its been a huge pain trying to get it to work in anaconda.

I believe it would be easier if I knew the name of the type of graph that is 'standard format' for displaying neural networks.

Please let me know if there is a package that I missed that is made for performing this task.

Here is how I get the network to display now:

code for graph:

import networkx as nx

G = nx.MultiDiGraph()
ed = N2.dna.get_conns(weight=True)

G.add_weighted_edges_from(ed)
nx.draw_planar(G,with_labels=True,font_weight='bold')


ed
Out[32]: 
[[0, 3, -1],
 [1, 3, -1],
 [2, 3, -1],
 [0, 4, -1],
 [4, 5, -1],
 [5, 3, 100],
 [2, 4, 10]]

Answer:

Wish i understand you right.

Possible solution:

import networkx as nx
from networkx.drawing.nx_agraph import graphviz_layout

G = nx.DiGraph()
ed = [[0, 4, -1],
 [0, 5, -1],
 [1, 4, -1],
 [1, 5, -1],
 [2, 4, -1],
 [2, 5, 10],
 [4, 3, -1],
 [5, 3, 100]]

G.add_weighted_edges_from(ed)
pos = graphviz_layout(G, prog='dot', args="-Grankdir=LR")
nx.draw(G,with_labels=True,pos=pos, font_weight='bold')