public class Network
extends java.lang.Object
implements java.io.Serializable
Weighted nodes and weighted edges are supported. Directed edges are not supported.
Network objects are immutable.
The adjacency matrix of the network is stored in a sparse compressed format.
Modifier and Type | Class and Description |
---|---|
class |
Network.RangeIterable
Iterable starting from a certain element to a certain element.
|
class |
Network.RangeIterator
Iterator capable of iterating over a specified range.
|
Modifier and Type | Field and Description |
---|---|
protected LargeDoubleArray |
edgeWeights
Edge weights.
|
protected long[] |
firstNeighborIndices
Index of the first neighbor of each node in the (@code neighbors} array.
|
protected long |
nEdges
Number of edges.
|
protected LargeIntArray |
neighbors
Neighbors of each node.
|
protected int |
nNodes
Number of nodes.
|
protected double[] |
nodeWeights
Node weights.
|
protected double |
totalEdgeWeightSelfLinks
Total edge weight of self links.
|
Constructor and Description |
---|
Network(double[] nodeWeights,
LargeIntArray[] edges,
boolean sortedEdges,
boolean checkIntegrity)
Constructs a network based on a list of edges.
|
Network(double[] nodeWeights,
LargeIntArray[] edges,
LargeDoubleArray edgeWeights,
boolean sortedEdges,
boolean checkIntegrity)
Constructs a network based on a list of edges.
|
Network(double[] nodeWeights,
long[] firstNeighborIndices,
LargeIntArray neighbors,
boolean checkIntegrity)
Constructs a network based on a list of neighbors.
|
Network(double[] nodeWeights,
long[] firstNeighborIndices,
LargeIntArray neighbors,
LargeDoubleArray edgeWeights,
boolean checkIntegrity)
Constructs a network based on a list of neighbors.
|
Network(int nNodes,
boolean setNodeWeightsToTotalEdgeWeights,
LargeIntArray[] edges,
boolean sortedEdges,
boolean checkIntegrity)
Constructs a network based on a list of edges.
|
Network(int nNodes,
boolean setNodeWeightsToTotalEdgeWeights,
LargeIntArray[] edges,
LargeDoubleArray edgeWeights,
boolean sortedEdges,
boolean checkIntegrity)
Constructs a network based on a list of edges.
|
Network(int nNodes,
boolean setNodeWeightsToTotalEdgeWeights,
long[] firstNeighborIndices,
LargeIntArray neighbors,
boolean checkIntegrity)
Constructs a network based on a list of neighbors.
|
Network(int nNodes,
boolean setNodeWeightsToTotalEdgeWeights,
long[] firstNeighborIndices,
LargeIntArray neighbors,
LargeDoubleArray edgeWeights,
boolean checkIntegrity)
Constructs a network based on a list of neighbors.
|
Modifier and Type | Method and Description |
---|---|
void |
checkIntegrity()
Checks the integrity of the network.
|
Network |
createNetworkWithoutEdgeWeights()
Creates a copy of the network, but without edge weights.
|
Network |
createNetworkWithoutNodeAndEdgeWeights()
Creates a copy of the network, but without node and edge weights.
|
Network |
createNetworkWithoutNodeWeights()
Creates a copy of the network, but without node weights.
|
Network |
createNormalizedNetworkUsingAssociationStrength()
Creates a copy of the network in which the edge weights have been
normalized using the association strength.
|
Network |
createNormalizedNetworkUsingFractionalization()
Creates a copy of the network in which the edge weights have been
normalized using fractionalization.
|
Network |
createPrunedNetwork(int maxNEdges)
Creates a copy of the network that has been pruned in order to have a
specified maximum number of edges.
|
Network |
createPrunedNetwork(long maxNEdges,
java.util.Random random)
Creates a copy of the network that has been pruned in order to have a
specified maximum number of edges.
|
Network |
createReducedNetwork(Clustering clustering)
Creates a reduced (or aggregate) network based on a clustering.
|
Network |
createSubnetwork(boolean[] nodesInSubnetwork)
Creates an induced subnetwork for specified nodes.
|
Network |
createSubnetwork(Clustering clustering,
int cluster)
Creates an induced subnetwork for a specified cluster in a clustering.
|
Network |
createSubnetwork(int[] nodes)
Creates an induced subnetwork for specified nodes.
|
Network |
createSubnetworkLargestComponent()
Creates an induced subnetwork of the largest connected component.
|
Network[] |
createSubnetworks(Clustering clustering)
Creates induced subnetworks for the clusters in a clustering.
|
LargeDoubleArray.FromToIterable |
edgeWeights(int node)
Returns an iterable over all the edge weights of all incident edges of a
node.
|
LargeIntArray[] |
getEdges()
Returns the list of edges.
|
LargeDoubleArray |
getEdgeWeights()
Returns the edge weights.
|
double[] |
getEdgeWeights(int node)
Returns the list of edge weights of a node.
|
double[][] |
getEdgeWeightsPerNode()
Returns a list of edge weights per node.
|
long |
getNEdges()
Returns the number of edges.
|
int[] |
getNeighbors(int node)
Returns the list of neighbors of a node.
|
int[][] |
getNeighborsPerNode()
Returns a list of neighbors per node.
|
int |
getNNeighbors(int node)
Returns the number of neighbors of a node.
|
int[] |
getNNeighborsPerNode()
Returns the number of neighbors per node.
|
int |
getNNodes()
Returns the number of nodes.
|
double |
getNodeWeight(int node)
Returns the weight of a node.
|
double[] |
getNodeWeights()
Returns the weight of each node.
|
double |
getTotalEdgeWeight()
Returns the total edge weight.
|
double |
getTotalEdgeWeight(int node)
Returns the total edge weight of a node.
|
double[] |
getTotalEdgeWeightPerNode()
Returns the total edge weight per node.
|
double |
getTotalEdgeWeightSelfLinks()
Returns the total edge weight of self links.
|
double |
getTotalNodeWeight()
Returns the total node weight.
|
Clustering |
identifyComponents()
Identifies the connected components of the network.
|
Network.RangeIterable |
incidentEdges(int node)
Returns an iterable over all the incident edges of a node.
|
static Network |
load(java.lang.String filename)
Loads a network from a file.
|
LargeIntArray.FromToIterable |
neighbors(int node)
Returns an iterable over all the neighbors of a node.
|
void |
save(java.lang.String filename)
Saves the network in a file.
|
static void |
sortEdges(LargeIntArray[] edges,
LargeDoubleArray edgeWeights)
Sorts a list of edges and the corresponding edge weights.
|
protected int nNodes
protected long nEdges
Each edge is counted twice, once in each direction.
protected double[] nodeWeights
protected long[] firstNeighborIndices
The neighbors of node i
are given by neighbors[firstNeighborIndices[i]], ...,
neighbors[firstNeighborIndices[i + 1] - 1]
.
protected LargeIntArray neighbors
protected LargeDoubleArray edgeWeights
protected double totalEdgeWeightSelfLinks
public Network(double[] nodeWeights, LargeIntArray[] edges, boolean sortedEdges, boolean checkIntegrity)
The list of edges is provided in the two-dimensional array edges
. Edge i
connects nodes edges[0].get(i)
and edges[1].get(i)
. Edges do not have weights. If sortedEdges
is
false, the list of edges does not need to be sorted and each edge must
be included only once. If sortedEdges
is true, the list of edges
must be sorted and each edge must be included twice, once in each
direction.
nodeWeights
- Node weightsedges
- Edge listsortedEdges
- Indicates whether the edge list is sortedcheckIntegrity
- Indicates whether to check the integrity of the
networkpublic Network(double[] nodeWeights, LargeIntArray[] edges, LargeDoubleArray edgeWeights, boolean sortedEdges, boolean checkIntegrity)
The list of edges is provided in the two-dimensional array edges
. Edge i
connects nodes edges[0].get(i)
and edges[1].get(i)
and has weight edgeWeights.get(i)
. If sortedEdges
is false, the list of edges does not need to be sorted and
each edge must be included only once. If sortedEdges
is true,
the list of edges must be sorted and each edge must be included twice,
once in each direction.
nodeWeights
- Node weightsedges
- Edge listedgeWeights
- Edge weightssortedEdges
- Indicates whether the edge list is sortedcheckIntegrity
- Indicates whether to check the integrity of the
networkpublic Network(double[] nodeWeights, long[] firstNeighborIndices, LargeIntArray neighbors, boolean checkIntegrity)
The list of neighbors is provided in the array neighbors
. The
neighbors of node i
are given by neighbors[firstNeighborIndices[i]], ...,
neighbors[firstNeighborIndices[i + 1] - 1]
. The array firstNeighborIndices
must have a length of the number of nodes plus 1.
The neighbors of a node must be listed in increasing order in the array
neighbors
. Edges do not have weights.
nodeWeights
- Node weightsfirstNeighborIndices
- Index of the first neighbor of each nodeneighbors
- Neighbor listcheckIntegrity
- Indicates whether to check the integrity of
the networkpublic Network(double[] nodeWeights, long[] firstNeighborIndices, LargeIntArray neighbors, LargeDoubleArray edgeWeights, boolean checkIntegrity)
The list of neighbors is provided in the array neighbors
. The
neighbors of node i
are given by neighbors[firstNeighborIndices[i]], ...,
neighbors[firstNeighborIndices[i + 1] - 1]
. The array firstNeighborIndices
must have a length of the number of nodes plus 1.
The neighbors of a node must be listed in increasing order in the array
neighbors
. For each neighbor in the array neighbors
, the
corresponding edge weight is provided in the array edgeWeights
.
nodeWeights
- Node weightsfirstNeighborIndices
- Index of the first neighbor of each nodeneighbors
- Neighbor listedgeWeights
- Edge weightscheckIntegrity
- Indicates whether to check the integrity of
the networkpublic Network(int nNodes, boolean setNodeWeightsToTotalEdgeWeights, LargeIntArray[] edges, boolean sortedEdges, boolean checkIntegrity)
The list of edges is provided in the two-dimensional array edges
. Edge i
connects nodes edges[0].get(i)
and edges[1].get(i)
. Edges do not have weights. If sortedEdges
is
false, the list of edges does not need to be sorted and each edge must
be included only once. If sortedEdges
is true, the list of edges
must be sorted and each edge must be included twice, once in each
direction.
If setNodeWeightsToTotalEdgeWeights
is false, the weights of the
nodes are set to 1. If setNodeWeightsToTotalEdgeWeights
is true,
the weight of a node is set equal to the total weight of the edges
between the node and its neighbors.
nNodes
- Number of nodessetNodeWeightsToTotalEdgeWeights
- Indicates whether to set node
weights equal to total edge
weightsedges
- Edge listsortedEdges
- Indicates whether the edge list
is sortedcheckIntegrity
- Indicates whether to check the
integrity of the networkpublic Network(int nNodes, boolean setNodeWeightsToTotalEdgeWeights, LargeIntArray[] edges, LargeDoubleArray edgeWeights, boolean sortedEdges, boolean checkIntegrity)
The list of edges is provided in the two-dimensional array edges
. Edge i
connects nodes edges[0].get(i)
and edges[1].get(i)
and has weight edgeWeights.get(i)
. If sortedEdges
is false, the list of edges does not need to be sorted and
each edge must be included only once. If sortedEdges
is true,
the list of edges must be sorted and each edge must be included twice,
once in each direction.
If setNodeWeightsToTotalEdgeWeights
is false, the weights of the
nodes are set to 1. If setNodeWeightsToTotalEdgeWeights
is true,
the weight of a node is set equal to the total weight of the edges
between the node and its neighbors.
nNodes
- Number of nodessetNodeWeightsToTotalEdgeWeights
- Indicates whether to set node
weights equal to total edge
weightsedges
- Edge listedgeWeights
- Edge weightssortedEdges
- Indicates whether the edge list
is sortedcheckIntegrity
- Indicates whether to check the
integrity of the networkpublic Network(int nNodes, boolean setNodeWeightsToTotalEdgeWeights, long[] firstNeighborIndices, LargeIntArray neighbors, boolean checkIntegrity)
The list of neighbors is provided in the array neighbors
. The
neighbors of node i
are given by neighbors[firstNeighborIndices[i]], ...,
neighbors[firstNeighborIndices[i + 1] - 1]
. The array firstNeighborIndices
must have a length of the number of nodes plus 1.
The neighbors of a node must be listed in increasing order in the array
neighbors
. Edges do not have weights.
If setNodeWeightsToTotalEdgeWeights
is false, the weights of the
nodes are set to 1. If setNodeWeightsToTotalEdgeWeights
is true,
the weight of a node is set equal to the total weight of the edges
between the node and its neighbors.
nNodes
- Number of nodessetNodeWeightsToTotalEdgeWeights
- Indicates whether to set node
weights equal to total edge
weightsfirstNeighborIndices
- Index of the first neighbor of
each nodeneighbors
- Neighbor listcheckIntegrity
- Indicates whether to check the
integrity of the networkpublic Network(int nNodes, boolean setNodeWeightsToTotalEdgeWeights, long[] firstNeighborIndices, LargeIntArray neighbors, LargeDoubleArray edgeWeights, boolean checkIntegrity)
The list of neighbors is provided in the array neighbors
. The
neighbors of node i
are given by neighbors[firstNeighborIndices[i]], ...,
neighbors[firstNeighborIndices[i + 1] - 1]
. The array firstNeighborIndices
must have a length of the number of nodes plus 1.
The neighbors of a node must be listed in increasing order in the array
neighbors
. For each neighbor in the array neighbors
, the
corresponding edge weight is provided in the array edgeWeights
.
If setNodeWeightsToTotalEdgeWeights
is false, the weights of the
nodes are set to 1. If setNodeWeightsToTotalEdgeWeights
is true,
the weight of a node is set equal to the total weight of the edges
between the node and its neighbors.
nNodes
- Number of nodessetNodeWeightsToTotalEdgeWeights
- Indicates whether to set node
weights equal to total edge
weightsfirstNeighborIndices
- Index of the first neighbor of
each nodeneighbors
- Neighbor listedgeWeights
- Edge weightscheckIntegrity
- Indicates whether to check the
integrity of the networkpublic static Network load(java.lang.String filename) throws java.lang.ClassNotFoundException, java.io.IOException
filename
- File from which a network is loadedjava.lang.ClassNotFoundException
- Class not foundjava.io.IOException
- Could not read the filesave(String filename)
public void save(java.lang.String filename) throws java.io.IOException
filename
- File in which the network is savedjava.io.IOException
- Could not write to the fileload(String filename)
public int getNNodes()
public double getTotalNodeWeight()
public double[] getNodeWeights()
public double getNodeWeight(int node)
node
- Nodepublic long getNEdges()
Each edge is counted only once, even though an edge runs in two
directions. This means that the number of edges returned by getEdges()
equals twice the number of edges returned by getNEdges()
.
public int[] getNNeighborsPerNode()
public int getNNeighbors(int node)
node
- Nodepublic LargeIntArray[] getEdges()
Each edge is included twice, once in each direction. This means that the
number of edges returned by getEdges()
equals twice the number
of edges returned by getNEdges()
.
The list of edges is returned in a two-dimensional array edges
.
Edge i
connects nodes edges[0].get(i)
and edges[1].get(i)
.
public int[][] getNeighborsPerNode()
public int[] getNeighbors(int node)
node
- Nodepublic LargeIntArray.FromToIterable neighbors(int node)
node
- Nodepublic Network.RangeIterable incidentEdges(int node)
node
- Nodepublic double getTotalEdgeWeight()
Each edge is considered only once, even though an edge runs in two
directions. This means that the sum of the edge weights returned by
getEdgeWeights()
equals twice the total edge weight returned by
getTotalEdgeWeight()
.
Edge weights of self links are not included.
public double[] getTotalEdgeWeightPerNode()
public double getTotalEdgeWeight(int node)
node
- Nodepublic LargeDoubleArray getEdgeWeights()
Each edge is included twice, once in each direction. This means that the
sum of the edge weights returned by getEdgeWeights()
equals
twice the total edge weight returned by getTotalEdgeWeight()
.
public double[][] getEdgeWeightsPerNode()
public double[] getEdgeWeights(int node)
node
- Nodepublic LargeDoubleArray.FromToIterable edgeWeights(int node)
node
- Nodepublic double getTotalEdgeWeightSelfLinks()
public Network createNetworkWithoutNodeWeights()
Each node is assigned a weight of 1.
public Network createNetworkWithoutEdgeWeights()
Each edge is assigned a weight of 1.
public Network createNetworkWithoutNodeAndEdgeWeights()
Each node is assigned a weight of 1, and each edge is assigned a weight of 1.
public Network createNormalizedNetworkUsingAssociationStrength()
The normalized weight a'[i][j]
of the edge between nodes i
and j
is given by
a'[i][j] = a[i][j] / (n[i] * n[j] / (2 * m))
,
where a[i][j]
is the non-normalized weight of the edge between
nodes i
and j
, n[i]
is the weight of node i
, and m
is half the total node weight.
If each node's weight equals the total weight of the edges between the node and its neighbors, the edge weights are normalized by dividing them by the expected edge weights in the random configuration model.
The node weights are set to 1.
public Network createNormalizedNetworkUsingFractionalization()
The normalized weight a'[i][j]
of the edge between nodes i
and j
is given by
a'[i][j] = a[i][j] * (n / n[i] + n / n[j]) / 2
,
where a[i][j]
is the non-normalized weight of the edge between
nodes i
and j
, n[i]
is the weight of node i
, and n
is the number of nodes.
The node weights are set to 1.
public Network createPrunedNetwork(int maxNEdges)
Only the edges with the highest weights are retained in the pruned network. In case of ties, the edges to be retained are selected randomly.
maxNEdges
- Maximum number of edgespublic Network createPrunedNetwork(long maxNEdges, java.util.Random random)
Only the edges with the highest weights are retained in the pruned network. In case of ties, the edges to be retained are selected randomly.
maxNEdges
- Maximum number of edgesrandom
- Random number generatorpublic Network createSubnetwork(int[] nodes)
nodes
- Nodespublic Network createSubnetwork(boolean[] nodesInSubnetwork)
nodesInSubnetwork
- Indicates the nodes to be included in the
subnetwork.public Network createSubnetwork(Clustering clustering, int cluster)
If subnetworks need to be created for all clusters in a clustering, it
is more efficient to use createSubnetworks(Clustering
clustering)
.
clustering
- Clusteringcluster
- Clusterpublic Network[] createSubnetworks(Clustering clustering)
clustering
- Clusteringpublic Network createSubnetworkLargestComponent()
public Network createReducedNetwork(Clustering clustering)
Each node in the reduced network corresponds to a cluster of nodes in the original network. The weight of a node in the reduced network equals the sum of the weights of the nodes in the corresponding cluster in the original network. The weight of an edge between two nodes in the reduced network equals the sum of the weights of the edges between the nodes in the two corresponding clusters in the original network.
clustering
- Clusteringpublic Clustering identifyComponents()
public void checkIntegrity() throws java.lang.IllegalArgumentException
It is checked whether:
An exception is thrown if the integrity of the network is violated.
java.lang.IllegalArgumentException
- An illegal argument was provided in the
construction of the network.public static void sortEdges(LargeIntArray[] edges, LargeDoubleArray edgeWeights)
edges
- Edge listedgeWeights
- Edge weights