networkit.linkprediction

class networkit.linkprediction.AdamicAdarIndex

Bases: _NetworKit.LinkPredictor

Implementation of the Adamic/Adar Index.

The index sums up the reciprocals of the logarithm of the degree of all common neighbors of u and v.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the Adamic/Adar Index of the given node-pair (u, v).

u : node
First node in graph.
v : node
Second node in graph.

The Adamic/Adar Index of the given node-pair (u, v).

class networkit.linkprediction.AdjustedRandIndex

Bases: _NetworKit.LinkPredictor

AdjustedRandIndex proposed by Hoffman et al. with natural threshold of 0.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the Adjusted Rand Index of the given node-pair (u, v).

u : node
First node in graph.
v : node
Second node in graph.

The Adjusted Rand Index of the given node-pair (u, v).

class networkit.linkprediction.AlgebraicDistanceIndex

Bases: _NetworKit.LinkPredictor

Algebraic distance assigns a distance value to pairs of nodes according to their structural closeness in the graph.

G : Graph
The graph to work on. Can be set to None and default is None.
numberSystems : count
Number of vectors/systems used for algebraic iteration.
numberIterations : count
Number of iterations in each system.
omega : double, optional
Overrelaxation parameter, default: 0.5.
norm : index, optional
The norm factor of the extended algebraic distance. Maximum norm is realized by setting the norm to 0. Default: 2.
preprocess(self)

Executes necessary initializations.

Starting with random initialization, compute for all numberSystems “diffusion” systems the situation after numberIterations iterations of overrelaxation with overrelaxation parameter omega.

REQ: Needs to be called before algdist delivers meaningful results!

run(self, node u, node v)

Returns the extended algebraic distance between node u and node v in the norm specified in the constructor.

u : node
The first node.
v : node
The second node.

Extended algebraic distance between the two nodes.

class networkit.linkprediction.CommonNeighborsIndex

Bases: _NetworKit.LinkPredictor

The CommonNeighborsIndex calculates the number of common neighbors of a node-pair in a given graph.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the number of common neighbors of the given nodes u and v.

u : node
First node in graph.
v : node
Second node in graph.

The number of common neighbors of u and v.

class networkit.linkprediction.Graph

Bases: object

An undirected graph (with optional weights) and parallel iterator methods.

Graph(n=0, weighted=False, directed=False)

Create a graph of n nodes. The graph has assignable edge weights if weighted is set to True. If weighted is set to False each edge has edge weight 1.0 and any other weight assignment will be ignored.

n : count, optional
Number of nodes.
weighted : bool, optional
If set to True, the graph can have edge weights other than 1.0.
directed : bool, optional
If set to True, the graph will be directed.
BFSEdgesFrom(self, node start, callback)

Experimental BFS search interface that passes edges that are part of the BFS tree to the callback

start: node
The start node from which the BFS shall be started
callback : object
Any callable object that takes the parameter (node, node)
BFSfrom(self, start, callback)

Experimental BFS search interface

start: node or list[node]
One or more start nodes from which the BFS shall be started
callback : object
Any callable object that takes the parameter (node, count) (the second parameter is the depth)
DFSEdgesFrom(self, node start, callback)

Experimental DFS search interface that passes edges that are part of the DFS tree to the callback

start: node
The start node from which the DFS shall be started
callback : object
Any callable object that takes the parameter (node, node)
DFSfrom(self, node start, callback)

Experimental DFS search interface

start: node
The start node from which the DFS shall be started
callback : object
Any callable object that takes the parameter node
addEdge(self, u, v, w=1.0)

Insert an undirected edge between the nodes u and v. If the graph is weighted you can optionally set a weight for this edge. The default weight is 1.0.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight, optional
Edge weight.
addNode(self)

Add a new node to the graph and return it.

node
The new node.
append(self, Graph G)

Appends another graph to this graph as a new subgraph. Performs node id remapping.

G : Graph

checkConsistency(self)

Check for invalid graph states, such as multi-edges.

compactEdges(self)

Compact the edge storage, this should be called after executing many edge deletions.

copyNodes(self)

Copies all nodes to a new graph

Graph
Graph with the same nodes (without edges)
degree(self, u)

Get the number of neighbors of v.

v : node
Node.
count
The number of neighbors.
degreeIn(self, u)
degreeOut(self, u)
density(self)

Get the density of the graph.

double

edgeId(self, node u, node v)
edgeid
id of the edge
edges(self)

Get list of edges as node pairs.

list
List of edges as node pairs.
forEdges(self, callback)

Experimental edge iterator interface

callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forEdgesOf(self, node u, callback)

Experimental incident (outgoing) edge iterator interface

u : node
The node of which incident edges shall be passed to the callback
callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forInEdgesOf(self, node u, callback)

Experimental incident incoming edge iterator interface

u : node
The node of which incident edges shall be passed to the callback
callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forNodePairs(self, callback)

Experimental node pair iterator interface

callback : object
Any callable object that takes the parameters (node, node)
forNodes(self, callback)

Experimental node iterator interface

callback : object
Any callable object that takes the parameter node
forNodesInRandomOrder(self, callback)

Experimental node iterator interface

callback : object
Any callable object that takes the parameter node
getCoordinate(self, v)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.

Get the coordinates of node v. Parameters ———- v : node

Node.
pair[float, float]
x and y coordinates of v.
getName(self)

Get the name of the graph.

string
The name of the graph.
hasEdge(self, u, v)

Checks if undirected edge {u,`v`} exists in the graph.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
bool
True if the edge exists, False otherwise.
hasEdgeIds(self)

Returns true if edges have been indexed

bool
if edges have been indexed
hasNode(self, u)

Checks if the Graph has the node u, i.e. if u hasn’t been deleted and is in the range of valid ids.

u : node
Node
bool
If the Graph has the node u
increaseWeight(self, u, v, w)

Increase the weight of an edge. If the edge does not exist, it will be inserted.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight
Edge weight.
indexEdges(self, bool force=False)

Assign integer ids to edges.

force : bool
Force re-indexing of edges.
initCoordinates(self)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.
isDirected(self)
isIsolated(self, u)

If the node u is isolated

u : node
Node.
bool
If the node is isolated
isWeighted(self)
bool
True if this graph supports edge weights other than 1.0.
merge(self, Graph G)
Modifies this graph to be the union of it and another graph.
Nodes with the same ids are identified with each other.

G : Graph

neighbors(self, u)

Get list of neighbors of u.

u : node
Node.
list
List of neighbors of `u.
nodes(self)

Get list of all nodes.

list
List of all nodes.
numberOfEdges(self)

Get the number of edges in the graph.

count
The number of edges.
numberOfNodes(self)

Get the number of nodes in the graph.

count
The number of nodes.
numberOfSelfLoops(self)

Get number of self-loops, i.e. edges {v, v}. Returns ——- count

number of self-loops.
randomEdge(self, bool uniformDistribution=False)

Get a random edge of the graph.

uniformDistribution : bool
If the distribution of the edge shall be uniform
pair
Random random edge.

Fast, but not uniformly random if uniformDistribution is not set, slow and uniformly random otherwise.

randomEdges(self, count numEdges)

Returns a list with numEdges random edges. The edges are chosen uniformly at random.

numEdges : count
The number of edges to choose.
list of pairs
The selected edges.
randomNeighbor(self, u)

Get a random neighbor of v and none if degree is zero.

v : node
Node.
node
A random neighbor of `v.
randomNode(self)

Get a random node of the graph.

node
A random node.
removeEdge(self, u, v)

Removes the undirected edge {u,`v`}.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
removeNode(self, u)

Remove a node v and all incident edges from the graph.

Incoming as well as outgoing edges will be removed.

u : node
Node.
removeSelfLoops(self)

Removes all self-loops from the graph.

restoreNode(self, u)

Restores a previously deleted node u with its previous id in the graph.

u : node
Node.
setCoordinate(self, v, value)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.

Set the coordinates of node v. Parameters ———- v : node

Node.
value : pair[float, float]
x and y coordinates of v.
setName(self, name)

Set name of graph to name.

name : string
The name.
setWeight(self, u, v, w)

Set the weight of an edge. If the edge does not exist, it will be inserted.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight
Edge weight.
size(self)

Get the size of the graph.

tuple
a pair (n, m) where n is the number of nodes and m is the number of edges
sortEdges(self)

Sorts the adjacency arrays by node id. While the running time is linear this temporarily duplicates the memory.

subgraphFromNodes(self, nodes)

Create a subgraph induced by the set nodes.

nodes : list
A subset of nodes of G which induce the subgraph.
Graph
The subgraph induced by nodes.

The returned graph G’ is isomorphic (structurally identical) to the subgraph in G, but node indices are not preserved.

swapEdge(self, node s1, node t1, node s2, node t2)

Changes the edge (s1, t1) into (s1, t2) and the edge (s2, t2) into (s2, t1).

If there are edge weights or edge ids, they are preserved. Note that no check is performed if the swap is actually possible, i.e. does not generate duplicate edges.

s1 : node
Source node of the first edge
t1 : node
Target node of the first edge
s2 : node
Source node of the second edge
t2 : node
Target node of the second edge
toString(self)

Get a string representation of the graph.

string
A string representation of the graph.
toUndirected(self)

Return an undirected version of this graph.

undirected graph.
toUnweighted(self)

Return an unweighted version of this graph.

graph.
totalEdgeWeight(self)

Get the sum of all edge weights.

edgeweight
The sum of all edge weights.
transpose(self)

Return the transpose of this (directed) graph.

directed graph.
upperEdgeIdBound(self)

Get an upper bound for the edge ids in the graph

count
An upper bound for the edge ids in the graph
upperNodeIdBound(self)

Get an upper bound for the node ids in the graph

count
An upper bound for the node ids in the graph
weight(self, u, v)

Get edge weight of edge {u , v}. Returns 0 if edge does not exist.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
edgeweight
Edge weight of edge {u , v} or 0 if edge does not exist.
weightedDegree(self, v)

Returns the weighted degree of v.

For directed graphs this is the sum of weights of all outgoing edges of v.

v : node
Node.
double
The weighted degree of v.
class networkit.linkprediction.JaccardIndex

Bases: _NetworKit.LinkPredictor

Implementation of the Jaccard index which normalizes the Common Neighbors Index.

This is done through dividing the number of common neighbors by the number of nodes in the neighboorhood-union.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the Jaccard index for the given node-pair (u, v).

u : node
First node in graph.
v : node
Second node in graph.

The Jaccard index for the given node-pair (u, v).

class networkit.linkprediction.KatzIndex

Bases: _NetworKit.LinkPredictor

Implementation of the Katz index.

Katz index assigns a pair of nodes a similarity score that is based on the sum of the weighted number of paths of length l where l is smaller than a given limit.

G : Graph, optional
The graph to operate on. Defaults to None.
maxPathLength : count, optional
Maximal length of the paths to consider. Defaults to 5.
dampingValue : double, optional
Used to exponentially damp every addend of the sum. Should be in (0, 1]. Defaults to 0.005.
run(self, node u, node v)

Returns the similarity score for the given node-pair based on the Katz index specified during construction.

The algorithm considers all paths starting at the node with the smaller degree except the algorithm started at the other node at the last call.

u : node
First node in graph.
v : node
Second node in graph.

The similarity score of the given node-pair calculated by the specified Katz index.

class networkit.linkprediction.LinkThresholder

Bases: object

Filters given predictions based on some criterion and returns a vector of node-pairs that fulfill the given criterion.

This can be used to determine which node-pairs should actually be interpreted as future links and which shouldn’t.

static byCount(vector[pair[pair[node,node],double]] predictions, count numLinks)

Returns the first numLinks highest scored node-pairs.

predictions : vector[pair[pair[node, node], double]].
Predictions to filter.
numLinks : count
Number of top-scored node-pairs to return.

The first numLinks highest scored node-pairs.

static byPercentage(vector[pair[pair[node,node],double]] predictions, double percentageLinks)

Returns the first percentageLinks percent of the highest scores node-pairs.

predictions : vector[pair[pair[node, node], double]].
Predictions to filter.
percentageLinks : double
Percentage of highest scored node-pairs to return.

The first percentageLinks percent of the highest scores node-pairs.

static byScore(vector[pair[pair[node,node],double]] predictions, double minScore)

Returns the node-pairs whose scores are at least equal to the given minScore.

predictions : vector[pair[pair[node, node], double]].
Predictions to filter.
minScore : double
Minimal score that the returned node-pairs should have.

A vector of node-pairs whose scores are at least equal to the given minScore.

class networkit.linkprediction.MissingLinksFinder

Bases: object

Allows the user to find missing links in the given graph.

The absent links to find are narrowed down by providing a distance that the nodes of the missing links should have. For example in case of distance 2 only node-pairs that would close a triangle in the given graph get returned.

G : Graph
The graph to find missing links in.
findAtDistance(self, count k)

Returns all missing links in the graph that have distance k.

Note that a distance of k actually means that there are k different links on the path of the two nodes that are connected through that path.

k : count
Distance of the absent links.

An ascendingly sorted vector of node-pairs where there is a missing link of distance k between the two nodes.

findFromNode(self, node u, count k)

Returns all missing links in the graph that have distance k and are connected to u.

Note that a distance of k actually means that there are k different links on the path of the two nodes that are connected through that path.

u : node
Node to find missing links from.
k : count
Distance of the absent links.

A vector of node-pairs where there is a missing link of distance k between the given node u and another node in the graph.

class networkit.linkprediction.NeighborhoodDistanceIndex

Bases: _NetworKit.LinkPredictor

Assigns a distance value to pairs of nodes according to the overlap of their neighborhoods.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the Neighborhood Distance index for the given node-pair (u, v).

u : node
First node in graph.
v : node
Second node in graph.

The Neighborhood Distance index for the given node-pair (u, v).

class networkit.linkprediction.NeighborsMeasureIndex

Bases: _NetworKit.LinkPredictor

Implementation of the Neighbors Measure Index.

This index is also known as Friends Measure and simply returns the number of connections between neighbors of the given nodes u and v.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the number of connections between neighbors of u and v.

u : node
First node in graph.
v : node
Second node in graph.

The number of connections between neighbors of u and v.

class networkit.linkprediction.PrecisionRecallMetric

Bases: _NetworKit.EvaluationMetric

Provides points that define the Precision-Recall curve for a given set of predictions.

Based on the generated points the area under the curve can be calculated with the trapzoidal rule.

testGraph : Graph, optional
Graph containing the links to use for evaluation. Defaults to None.
getCurve(self, vector[pair[pair[node,node],double]] predictions, count numThresholds=1000)

Generates the points for the Precision-Recall curve with respect to the given predictions.

The curve assigns every recall-value a corresponding precision as the y-value. In case of a tie regarding multiple y-values for a x-value the smallest (= latest) y-value will be used.

predictions : vector[pair[pair[node, node], double]]
Predictions to evaluate.
numThresholds : count, optional
The number of thresholds to use the metric on. Defaults to 1000.

A pair of vectors where the first vector contains all recall-values and the second vector the corresponding precision-values.

class networkit.linkprediction.PredictionsSorter

Bases: object

Allows the sorting of predictions by score or node-pair.

static sortByNodePair(list predictions)

Sorts the predictions ascendingly by node-pair.

This means for example (0, 0) < (0, 1) and (1, 1) < (1, 0).

predictions : vector[pair[pair[node, node], double]]
The predictions to sort.
static sortByScore(list predictions)

Sorts the given predictions descendingly by score.

In case there is a tie the node-pairs are used as a tie-breaker by sorting them ascendingly on the first node and on a tie ascendingly by the second node.

predictions : vector[pair[pair[node, node], double]]
The predictions to sort.
class networkit.linkprediction.PreferentialAttachmentIndex

Bases: _NetworKit.LinkPredictor

Implementation of the Preferential Attachment Index.

The run-method simply calculates the product of the number of nodes in the neighborhoods regarding the given nodes.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the product of the cardinalities of the neighborhoods regarding u and v.

u : node
First node in graph.
v : node
Second node in graph.

The product of the cardinalities of the neighborhoods regarding u and v

class networkit.linkprediction.ROCMetric

Bases: _NetworKit.EvaluationMetric

Provides points that define the Receiver Operating Characteristic curve for a given set of predictions.

Based on the generated points the area under the curve can be calculated with the trapzoidal rule.

testGraph : Graph, optional
Graph containing the links to use for evaluation. Defaults to None.
getCurve(self, vector[pair[pair[node,node],double]] predictions, count numThresholds=1000)

Generate the points of the Receiver Operating Characteristic curve regarding the previously set predictions.

Note that in the case of multiple y-values mapping to the same x-value the highest (=latest) y-value gets picked.

predictions : vector[pair[pair[node, node], double]]
Predictions to evaluate.
numThresholds : count, optional
The number of thresholds to use the metric on. Defaults to 1000.

A pair of vectors where the first vector contains the false positive rates and the second vector the corresponding true positive rates.

class networkit.linkprediction.RandomLinkSampler

Bases: object

Provides methods to randomly sample a number of edges from a given graph.

static byCount(Graph G, count numLinks)

Returns a graph that contains numLinks links from the given graph G.

The links are randomly selected from G until the given count is reached.

G : Graph
The graph to construct the training graph from.
numLinks : count
Number of links the returned graph should consist of.

A graph that contains the given number of links from G.

static byPercentage(Graph G, double percentage)

Returns a graph that contains percentage percent of links form the given graph G.

The links are randomly selected from G until the given percentage is reached.

G : Graph
The graph to construct the training graph from.
percentage : double
Percentage of links regarding the number of links in the given graph that should be in the returned graph.

A graph that contains the given percentage of links from G.

class networkit.linkprediction.ResourceAllocationIndex

Bases: _NetworKit.LinkPredictor

Implementation of the ResourceAllocationIndex.

The index is similar to Adamic/Adar and sums up the reciprocals of the degree of all common neighbors of u and v.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the Resource Allocation Index of the given node-pair (u, v).

u : node
First node in graph.
v : node
Second node in graph.

The Resource Allocation Index of the given node-pair (u, v).

class networkit.linkprediction.SameCommunityIndex

Bases: _NetworKit.LinkPredictor

Index to determine whether two nodes are in the same community.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns 1 if the given nodes u and v are in the same community, 0 otherwise.

u : node
First node in graph.
v : node
Second node in graph.

1 if the given nodes u and v are in the same community, 0 otherwise.

class networkit.linkprediction.TotalNeighborsIndex

Bases: _NetworKit.LinkPredictor

Implementation of the Total Neighbors Index.

This index is also known as Total Friends Index and returns the number of nodes in the neighborhood-union of u and v.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the number of total union-neighbors for the given node-pair (u, v).

u : node
First node in graph.
v : node
Second node in graph.

The number of total union-neighbors for the given node-pair (u, v).

class networkit.linkprediction.UDegreeIndex

Bases: _NetworKit.LinkPredictor

Index that simply returns the degree of the first given node.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the degree of the first node provided, namely u.

u : node
First node in graph.
v : node
Second node in graph.

The degree of the first node provided, namely u.

class networkit.linkprediction.VDegreeIndex

Bases: _NetworKit.LinkPredictor

Index that simply returns the degree of the second given node.

G : Graph, optional
The graph to work on. Defaults to None.
run(self, node u, node v)

Returns the degree of the second node provided, namely v.

u : node
First node in graph.
v : node
Second node in graph.

The degree of the second node provided, namely v.

networkit.linkprediction.getFeatures(nodePairs, *linkPredictors)

Returns a numpy-array containing the generated scores from the predictors for the given node-pairs.

nodePairs : vector[pair[node, node]]
Node-pairs to get the samples for.
*linkPredictors
List of link predictors to use for sample-generation.

A numpy-array of shape (#nodePairs, #linkPredictors) containing the generated scores from the predictors for the given node-pairs.

networkit.linkprediction.getLabels(nodePairs, G)

Returns a numpy-array containing the labels of the given node-pairs.

The labels are defined as follows: 1 = link, 0 = absent link.

nodePairs : vector[pair[node, node]]
Node-pairs to get the labels for.
G : Graph
Graph which provides ground truth for the labels.

A numpy-array containing the labels of the given node-pairs.

networkit.linkprediction.trainClassifier(trainingSet, trainingGraph, classifier, *linkPredictors)

Trains the given classifier with the feature-vectors generated by the given linkPredictors.

trainingSet : vector[pair[node, node]]
Vector of node-pairs to generate features for,
trainingGraph : Graph
Training graph containing all edges from the training set.
classifier:
Scikit-learn classifier to train.
linkPredictors:
Predictors used for the generation of feature-vectors.