| Title: | Incremental Graphlet Counting for Network Optimisation |
|---|---|
| Description: | An efficient and incremental approach for calculating the differences in orbit counts when performing single edge modifications in a network. Calculating the differences in orbit counts is much more efficient than recalculating all orbit counts from scratch for each time point. |
| Authors: | Robrecht Cannoodt [aut, cre] (<https://orcid.org/0000-0003-3641-729X>, rcannood) |
| Maintainer: | Robrecht Cannoodt <[email protected]> |
| License: | GPL-3 |
| Version: | 1.0.2 |
| Built: | 2024-11-07 02:40:46 UTC |
| Source: | https://github.com/rcannood/incgraph |
calculate.delta calculates the changes in orbit counts as a result of a single edge modification.
calculate.delta(network, i, j)calculate.delta(network, i, j)
network |
An instance of the incgraph.network class |
i |
A node in |
j |
A node in |
This method iterates over and counts all graphlets which were added to or removed from the network due to one edge modification.
A list containing two N-by-73 matrices, with N the number of nodes in the network and 1 column for each possible orbit.
The value of list$add[i,j] (resp. list$rem[i,j]) is the number of times a subgraph was added to (resp. removed from)
the network such that node i has orbit j in that subgraph.
Cannoodt Robrecht, [email protected]
Cannoodt, R. et al. (2015) IncGraph: A graphlet-based approach for characterising topological changes in evolving networks. Submitted to Bioinformatics.
See new.incgraph.network for examples and usage.
calculate.orbit.counts calculates the orbit counts of the current network.
calculate.orbit.counts(network)calculate.orbit.counts(network)
network |
An instance of the incgraph.network class |
The complete orbit counts is calcucated using the count5 from the orca package.
Calling this method repeatedly becomes very inefficient for evolving networks. For evolving networks, the usage
of calculate.delta is recommended.
For more details on this method, see Hočevar and Demšar (2014).
An N-by-73 matrix, with N the number of nodes in the network and 1 column for each possible orbit.
The value of mat[i,j] is the number of times node i has orbit j in a subgraph in the network.
Hočevar, T. and Demšar J. (2014) A combinatorial approach to graphlet counting. Bioinformatics.
See new.incgraph.network for examples and usage.
contains returns TRUE if the network contains the edge (i, j).
contains(network, i, j)contains(network, i, j)
network |
An instance of the incgraph.network class |
i |
A node in |
j |
A node in |
TRUE if the network contains (i, j)
See new.incgraph.network for examples and usage.
flip modifies an edge in the network. If it is contained in the network, it is removed from the network, otherwise it is added to the network.
flip(network, i, j)flip(network, i, j)
network |
An instance of the incgraph.network class |
i |
A node in |
j |
A node in |
See new.incgraph.network for examples and usage.
Generate a dynamic network
generate.dynamic.network( model, amnt.nodes, amnt.edges, amnt.operations, trace = T, ...) generate.geometric(amnt.nodes, amnt.edges, amnt.operations, amnt.dimensions = 3, trace = T) generate.barabasialbert(amnt.nodes, amnt.edges, amnt.operations, offset.exponent = 1, trace = T) generate.erdosrenyi(amnt.nodes, amnt.edges, amnt.operations, trace = T)generate.dynamic.network( model, amnt.nodes, amnt.edges, amnt.operations, trace = T, ...) generate.geometric(amnt.nodes, amnt.edges, amnt.operations, amnt.dimensions = 3, trace = T) generate.barabasialbert(amnt.nodes, amnt.edges, amnt.operations, offset.exponent = 1, trace = T) generate.erdosrenyi(amnt.nodes, amnt.edges, amnt.operations, trace = T)
model |
The network model with which to generate the network; |
amnt.nodes |
the number of nodes in the network at any given type |
amnt.edges |
the number of edges in the network at any given type |
amnt.operations |
the number of edge additions/deletions to generate |
trace |
will print output text if |
... |
extra parameters to pass to a specific network generator |
amnt.dimensions |
(only GEO) the number of dimensions in which to operate |
offset.exponent |
(only BA) the offset exponent for the weighted sampling |
A list containing the starting network network and the dynamic operations peformed on it operations.
# dyn.net.ba <- generate.dynamic.network("BA", 300, 300, 1000) dyn.net.er <- generate.dynamic.network("ER", 300, 300, 1000) dyn.net.geo <- generate.dynamic.network("GEO", 300, 300, 1000)# dyn.net.ba <- generate.dynamic.network("BA", 300, 300, 1000) dyn.net.er <- generate.dynamic.network("ER", 300, 300, 1000) dyn.net.geo <- generate.dynamic.network("GEO", 300, 300, 1000)
get.neighbours returns a vector of all neighbours of i.
get.neighbours(network, i)get.neighbours(network, i)
network |
An instance of the incgraph.network class |
i |
A node in |
Returns all neighbours of node i
See new.incgraph.network for examples and usage.
IncGraph: incremental graphlet counting for network optimisation
Cannoodt Robrecht, [email protected]
Cannoodt, R. et al. (2017) IncGraph: incremental graphlet counting for network optimisation. Under submission.
new.incgraph.network, calculate.orbit.counts, calculate.delta
# Create a new (empty) network with 4 nodes net <- new.incgraph.network(amnt.nodes = 4) # Create a new network with 4 nodes and some edges net <- new.incgraph.network(links = matrix(c(1, 2, 2, 3, 1, 4), ncol=2)) # Create a new network with 10 nodes and some edges net <- new.incgraph.network(amnt.nodes = 10, links = matrix(c(1, 2, 2, 3, 1, 4), ncol=2)) # Create a more complex network from a matrix mat <- matrix(c(1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 2, 7, 2, 8, 2, 9, 2, 10), ncol=2) net <- new.incgraph.network(links=mat) # Calculate the initial orbit counts using orca orb.counts <- calculate.orbit.counts(net) # Modify an edge and calculate the differences in orbit counts flip(net, 5, 10) # add (5,10) delta1 <- calculate.delta(net, 5, 10) # Modify another edge flip(net, 6, 10) # add (6, 10) delta2 <- calculate.delta(net, 6, 10) # And another flip(net, 1, 5) # remove (1, 5) delta3 <- calculate.delta(net, 1, 5) # Verify that the new orbit counts equals the old orbit counts plus the delta counts new.orb.counts.incremental <- orb.counts + delta1$add - delta1$rem + delta2$add - delta2$rem + delta3$add - delta3$rem new.orb.counts <- calculate.orbit.counts(net) all(new.orb.counts.incremental == new.orb.counts) # TRUE ## Additional helper functions # Transform the network to a matrix network.as.matrix(net) # Get all neighbours of a node get.neighbours(net, 1) # Does the network contain a specific interaction? contains(net, 5, 10) contains(net, 7, 10) # Reinitialise to an empty network reset(net) network.as.matrix(net)# Create a new (empty) network with 4 nodes net <- new.incgraph.network(amnt.nodes = 4) # Create a new network with 4 nodes and some edges net <- new.incgraph.network(links = matrix(c(1, 2, 2, 3, 1, 4), ncol=2)) # Create a new network with 10 nodes and some edges net <- new.incgraph.network(amnt.nodes = 10, links = matrix(c(1, 2, 2, 3, 1, 4), ncol=2)) # Create a more complex network from a matrix mat <- matrix(c(1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 2, 7, 2, 8, 2, 9, 2, 10), ncol=2) net <- new.incgraph.network(links=mat) # Calculate the initial orbit counts using orca orb.counts <- calculate.orbit.counts(net) # Modify an edge and calculate the differences in orbit counts flip(net, 5, 10) # add (5,10) delta1 <- calculate.delta(net, 5, 10) # Modify another edge flip(net, 6, 10) # add (6, 10) delta2 <- calculate.delta(net, 6, 10) # And another flip(net, 1, 5) # remove (1, 5) delta3 <- calculate.delta(net, 1, 5) # Verify that the new orbit counts equals the old orbit counts plus the delta counts new.orb.counts.incremental <- orb.counts + delta1$add - delta1$rem + delta2$add - delta2$rem + delta3$add - delta3$rem new.orb.counts <- calculate.orbit.counts(net) all(new.orb.counts.incremental == new.orb.counts) # TRUE ## Additional helper functions # Transform the network to a matrix network.as.matrix(net) # Get all neighbours of a node get.neighbours(net, 1) # Does the network contain a specific interaction? contains(net, 5, 10) contains(net, 7, 10) # Reinitialise to an empty network reset(net) network.as.matrix(net)
network.as.matrix returns the network as a matrix
network.as.matrix(network)network.as.matrix(network)
network |
An instance of the incgraph.network class |
See new.incgraph.network for examples and usage.
new.incgraph.network creates a new IncGraph object containing either
an empty network or a network initialised from a given matrix.
new.incgraph.network(amnt.nodes, links=NULL) new.incgraph.network(amnt.nodes=NULL, links) new.incgraph.network(amnt.nodes, links)new.incgraph.network(amnt.nodes, links=NULL) new.incgraph.network(amnt.nodes=NULL, links) new.incgraph.network(amnt.nodes, links)
amnt.nodes |
The number of nodes in the network |
links |
A matrix with 2 columns and N rows, 1 row for each edge to be loaded in the network |
This creates a new instance of the incgraph.network class. At least one of the parameters
(amnt.nodes or links) needs to be passed to this function.
Please note that this is a stateful object.
An instance of the incgraph.network class
incgraph, calculate.orbit.counts, calculate.delta
# Create a new (empty) network with 4 nodes net <- new.incgraph.network(amnt.nodes = 4) # Create a new network with 4 nodes and some edges net <- new.incgraph.network(links = matrix(c(1, 2, 2, 3, 1, 4), ncol=2)) # Create a new network with 10 nodes and some edges net <- new.incgraph.network(amnt.nodes = 10, links = matrix(c(1, 2, 2, 3, 1, 4), ncol=2)) # Create a more complex network from a matrix mat <- matrix(c(1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 2, 7, 2, 8, 2, 9, 2, 10), ncol=2) net <- new.incgraph.network(links=mat) # Calculate the initial orbit counts using orca orb.counts <- calculate.orbit.counts(net) # Modify an edge and calculate the differences in orbit counts flip(net, 5, 10) # add (5,10) delta1 <- calculate.delta(net, 5, 10) # Modify another edge flip(net, 6, 10) # add (6, 10) delta2 <- calculate.delta(net, 6, 10) # And another flip(net, 1, 5) # remove (1, 5) delta3 <- calculate.delta(net, 1, 5) # Verify that the new orbit counts equals the old orbit counts plus the delta counts new.orb.counts.incremental <- orb.counts + delta1$add - delta1$rem + delta2$add - delta2$rem + delta3$add - delta3$rem new.orb.counts <- calculate.orbit.counts(net) all(new.orb.counts.incremental == new.orb.counts) # TRUE ## Additional helper functions # Transform the network to a matrix network.as.matrix(net) # Get all neighbours of a node get.neighbours(net, 1) # Does the network contain a specific interaction? contains(net, 5, 10) contains(net, 7, 10) # Reinitialise to an empty network reset(net) network.as.matrix(net)# Create a new (empty) network with 4 nodes net <- new.incgraph.network(amnt.nodes = 4) # Create a new network with 4 nodes and some edges net <- new.incgraph.network(links = matrix(c(1, 2, 2, 3, 1, 4), ncol=2)) # Create a new network with 10 nodes and some edges net <- new.incgraph.network(amnt.nodes = 10, links = matrix(c(1, 2, 2, 3, 1, 4), ncol=2)) # Create a more complex network from a matrix mat <- matrix(c(1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 2, 7, 2, 8, 2, 9, 2, 10), ncol=2) net <- new.incgraph.network(links=mat) # Calculate the initial orbit counts using orca orb.counts <- calculate.orbit.counts(net) # Modify an edge and calculate the differences in orbit counts flip(net, 5, 10) # add (5,10) delta1 <- calculate.delta(net, 5, 10) # Modify another edge flip(net, 6, 10) # add (6, 10) delta2 <- calculate.delta(net, 6, 10) # And another flip(net, 1, 5) # remove (1, 5) delta3 <- calculate.delta(net, 1, 5) # Verify that the new orbit counts equals the old orbit counts plus the delta counts new.orb.counts.incremental <- orb.counts + delta1$add - delta1$rem + delta2$add - delta2$rem + delta3$add - delta3$rem new.orb.counts <- calculate.orbit.counts(net) all(new.orb.counts.incremental == new.orb.counts) # TRUE ## Additional helper functions # Transform the network to a matrix network.as.matrix(net) # Get all neighbours of a node get.neighbours(net, 1) # Does the network contain a specific interaction? contains(net, 5, 10) contains(net, 7, 10) # Reinitialise to an empty network reset(net) network.as.matrix(net)
orca.halfdelta calculates the orca counts for a network that has just been changed.
orca.halfdelta(network, i, j)orca.halfdelta(network, i, j)
network |
An instance of the incgraph.network class |
i |
A node in |
j |
A node in |
reset resets all the data structures so that all edges are removed from the network.
reset(network)reset(network)
network |
An instance of the incgraph.network class |
See new.incgraph.network for examples and usage.
set.network sets a given network to contain the given links.
set.network(network, links)set.network(network, links)
network |
An instance of the incgraph.network class |
links |
A matrix with 2 columns and N rows, 1 row for each edge to be loaded in the network |
This first resets the network and adds all given links. For minor changes to the network,
the usage of flip is recommended.
See new.incgraph.network for examples and usage.