How to identify unmatched nodes in a network
DISCLAIMER: This is a network science question but I am a biologist with no education in network science beyond my own reading. I'm also pretty bad at mathematics. Therefore this question is a little unfocused and I'll probably be making a bunch of rookie errors too.
I'm analysing a weighted directed network (70 nodes, 311 edges) and as part of my analysis I want to identify Driver Nodes (Liu et al, 2011; Liu and Barabasi, 2016; references below), which are unmatched nodes, if I understand these papers. Brief definitions:
Matching: a set of edges which do not share terminal nodes in common.
Matched nodes: terminating nodes of the edges in a matching set.
Unmatched nodes: nodes that do not connect to any of the edges in the matching set.
The only igraph functions I could find even related to this are the graph matching ones (
is_matching() etc.) created by @Tamás but these require an input vector of potential matchings, which I don't have nor understand (based on the documentation).
My question is, how can I identify unmatched nodes? I figure I need to identify all matching edges, then removing their associated matched nodes from the graph would leave behind just the driver nodes. But I don't even know where to start.
Here's an example of my graph:
g <- erdos.renyi.game(n = 70, p.or.m = 311, type = "gnm", directed = T, loops = F) E(g)$weight <- runif(length(E(g)), 1, 7) plot(g, edge.arrow.size = 0.4, vertex.label.cex = 0.7, edge.width = E(g)$weight*0.3, edge.arrow.width = 0.3, vertex.size = 10, vertex.size2 = 10, asp = 0.9, margin = -0.1)
Liu et al, 2011: Nature 473, 167–173 (12 May 2011) doi:10.1038/nature10011 (Especially final paragraph of Network Controllability.)
Liu and Barabasi, 2016: Rev. Mod. Phys. 88, 035006 – Published 6 September 2016 (Throughout Controllability of Linear System.)