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.
run
(self, node u, node v)Returns the Adamic/Adar Index of the given node-pair (u, v).
The Adamic/Adar Index of the given node-pair (u, v).
networkit.linkprediction.
AdjustedRandIndex
Bases: _NetworKit.LinkPredictor
AdjustedRandIndex proposed by Hoffman et al. with natural threshold of 0.
run
(self, node u, node v)Returns the Adjusted Rand Index of the given node-pair (u, v).
The Adjusted Rand Index of the given node-pair (u, v).
networkit.linkprediction.
AlgebraicDistanceIndex
Bases: _NetworKit.LinkPredictor
Algebraic distance assigns a distance value to pairs of nodes according to their structural closeness in the graph.
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.
Extended algebraic distance between the two nodes.
networkit.linkprediction.
CommonNeighborsIndex
Bases: _NetworKit.LinkPredictor
The CommonNeighborsIndex calculates the number of common neighbors of a node-pair in a given graph.
run
(self, node u, node v)Returns the number of common neighbors of the given nodes u and v.
The number of common neighbors of u and v.
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.
BFSEdgesFrom
(self, node start, callback)Experimental BFS search interface that passes edges that are part of the BFS tree to the callback
BFSfrom
(self, start, callback)Experimental BFS search interface
DFSEdgesFrom
(self, node start, callback)Experimental DFS search interface that passes edges that are part of the DFS tree to the callback
DFSfrom
(self, node start, callback)Experimental DFS search interface
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.
addNode
(self)Add a new node to the graph and return it.
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
degree
(self, u)Get the number of neighbors of v.
degreeIn
(self, u)degreeOut
(self, u)density
(self)Get the density of the graph.
double
edgeId
(self, node u, node v)edges
(self)Get list of edges as node pairs.
forEdges
(self, callback)Experimental edge iterator interface
forEdgesOf
(self, node u, callback)Experimental incident (outgoing) edge iterator interface
forInEdgesOf
(self, node u, callback)Experimental incident incoming edge iterator interface
forNodePairs
(self, callback)Experimental node pair iterator interface
forNodes
(self, callback)Experimental node iterator interface
forNodesInRandomOrder
(self, callback)Experimental node iterator interface
getCoordinate
(self, v)Get the coordinates of node v. Parameters ———- v : node
Node.
getName
(self)Get the name of the graph.
hasEdge
(self, u, v)Checks if undirected edge {u,`v`} exists in the graph.
hasEdgeIds
(self)Returns true 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.
increaseWeight
(self, u, v, w)Increase the weight of an edge. If the edge does not exist, it will be inserted.
indexEdges
(self, bool force=False)Assign integer ids to edges.
initCoordinates
(self)isDirected
(self)isIsolated
(self, u)If the node u is isolated
isWeighted
(self)merge
(self, Graph G)G : Graph
neighbors
(self, u)Get list of neighbors of u.
nodes
(self)Get list of all nodes.
numberOfEdges
(self)Get the number of edges in the graph.
numberOfNodes
(self)Get the number of nodes in the graph.
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.
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.
randomNeighbor
(self, u)Get a random neighbor of v and none if degree is zero.
randomNode
(self)Get a random node of the graph.
removeEdge
(self, u, v)Removes the undirected edge {u,`v`}.
removeNode
(self, u)Remove a node v and all incident edges from the graph.
Incoming as well as outgoing edges will be removed.
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.
setCoordinate
(self, v, value)Set the coordinates of node v. Parameters ———- v : node
Node.
setName
(self, name)Set name of graph to name.
setWeight
(self, u, v, w)Set the weight of an edge. If the edge does not exist, it will be inserted.
size
(self)Get the size of the graph.
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.
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.
toString
(self)Get 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.
transpose
(self)Return the transpose of this (directed) graph.
directed graph.
upperEdgeIdBound
(self)Get an upper bound for the edge ids in the graph
upperNodeIdBound
(self)Get 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.
weightedDegree
(self, v)Returns the weighted degree of v.
For directed graphs this is the sum of weights of all outgoing edges of v.
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.
run
(self, node u, node v)Returns the Jaccard index for the given node-pair (u, v).
The Jaccard index for the given node-pair (u, v).
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.
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.
The similarity score of the given node-pair calculated by the specified Katz index.
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.
byCount
(vector[pair[pair[node,node],double]] predictions, count numLinks)Returns the first numLinks highest scored node-pairs.
The first numLinks highest scored node-pairs.
byPercentage
(vector[pair[pair[node,node],double]] predictions, double percentageLinks)Returns the first percentageLinks percent of the highest scores node-pairs.
The first percentageLinks percent of the highest scores node-pairs.
byScore
(vector[pair[pair[node,node],double]] predictions, double minScore)Returns the node-pairs whose scores are at least equal to the given minScore.
A vector of node-pairs whose scores are at least equal to the given minScore.
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.
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.
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.
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.
networkit.linkprediction.
NeighborhoodDistanceIndex
Bases: _NetworKit.LinkPredictor
Assigns a distance value to pairs of nodes according to the overlap of their neighborhoods.
run
(self, node u, node v)Returns the Neighborhood Distance index for the given node-pair (u, v).
The Neighborhood Distance index for the given node-pair (u, v).
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.
run
(self, node u, node v)Returns the number of connections between neighbors of u and v.
The number of connections between neighbors of u and v.
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.
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.
A pair of vectors where the first vector contains all recall-values and the second vector the corresponding precision-values.
networkit.linkprediction.
PredictionsSorter
Bases: object
Allows the sorting of predictions by score or node-pair.
sortByNodePair
(list predictions)Sorts the predictions ascendingly by node-pair.
This means for example (0, 0) < (0, 1) and (1, 1) < (1, 0).
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.
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.
run
(self, node u, node v)Returns the product of the cardinalities of the neighborhoods regarding u and v.
The product of the cardinalities of the neighborhoods regarding u and v
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.
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.
A pair of vectors where the first vector contains the false positive rates and the second vector the corresponding true positive rates.
networkit.linkprediction.
RandomLinkSampler
Bases: object
Provides methods to randomly sample a number of edges from a given graph.
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.
A graph that contains the given number of links from G.
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.
A graph that contains the given percentage of links from G.
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.
run
(self, node u, node v)Returns the Resource Allocation Index of the given node-pair (u, v).
The Resource Allocation Index of the given node-pair (u, v).
networkit.linkprediction.
SameCommunityIndex
Bases: _NetworKit.LinkPredictor
Index to determine whether two nodes are in the same community.
run
(self, node u, node v)Returns 1 if the given nodes u and v are in the same community, 0 otherwise.
1 if the given nodes u and v are in the same community, 0 otherwise.
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.
run
(self, node u, node v)Returns the number of total union-neighbors for the given node-pair (u, v).
The number of total union-neighbors for the given node-pair (u, v).
networkit.linkprediction.
UDegreeIndex
Bases: _NetworKit.LinkPredictor
Index that simply returns the degree of the first given node.
run
(self, node u, node v)Returns the degree of the first node provided, namely u.
The degree of the first node provided, namely u.
networkit.linkprediction.
VDegreeIndex
Bases: _NetworKit.LinkPredictor
Index that simply returns the degree of the second given node.
run
(self, node u, node v)Returns the degree of the second node provided, namely v.
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.
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.
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.