Package | com.yworks.yfiles.algo |
Class | public class Centrality |
Inheritance | Centrality YObject Object |
Method | Defined By | ||
---|---|---|---|
Centrality(init:Boolean = true) | Centrality | ||
[static]
Computes the closeness centrality for the nodes of a graph. | Centrality | ||
degreeCentrality(graph:Graph, centrality:NodeMap, considerInEdges:Boolean, considerOutEdges:Boolean):void [static]
Computes the degree centrality for the nodes of a graph. | Centrality | ||
[static]
Computes betweenness centrality for each edge of a given graph. | Centrality | ||
equals(o:Object):Boolean | YObject | ||
getClass():Class [override] | Centrality | ||
[static]
Computes the graph centrality for the nodes of a graph. | Centrality | ||
hashCode():int | YObject | ||
[static] | Centrality | ||
[static]
Computes betweenness centrality for each node of a given graph. | Centrality | ||
nodeEdgeBetweenness(graph:Graph, nodeCentrality:NodeMap, edgeCentrality:EdgeMap, directed:Boolean, edgeCosts:DataProvider):void [static]
Computes betweenness centrality for each node and edge of a given graph. | Centrality | ||
[static]
Like normalizeNodeMap(), but for EdgeMap. | Centrality | ||
[static]
This method normalizes the double values of a node map by dividing all values by the maximum of all values (maximum norm). | Centrality | ||
weightCentrality(graph:Graph, centrality:NodeMap, considerInEdges:Boolean, considerOutEdges:Boolean, edgeWeights:DataProvider):void [static]
Computes the weight centrality for the nodes of a graph. | Centrality |
Method | Defined By | ||
---|---|---|---|
initCentrality():void | Centrality |
Centrality | () | Constructor |
public function Centrality(init:Boolean = true)
init:Boolean (default = true )
|
closenessCentrality | () | method |
public static function closenessCentrality(graph:Graph, closeness:NodeMap, directed:Boolean, edgeCosts:DataProvider):void
Computes the closeness centrality for the nodes of a graph. Closeness centrality is defined as the reciprocal of the sum of shortest path distances of a node to all other nodes in the graph. Therefore a node with high closeness centrality has short distances to all other nodes of a graph. Also note, that for unconnected graphs the centrality values of all nodes will be zero, since the distance to some nodes is infinite.
Precondition GraphChecker.isConnected(graph)
Complexity O(graph.N()^2 + graph.N()*graph.E()) for unweighted graphs, O( (graph.N()*graph.E()) + graph.N()^2 *log(graph.N())) or: O(graph.N()) * O(Uniform) for unweighted, O(allPairs) for weighted graphs
Parameters
graph:Graph — the input graph.
| |
closeness:NodeMap — return value. A map which hold the centrality value of type double for every node.
| |
directed:Boolean — whether to consider the edges of the graph as directed or undirected.
| |
edgeCosts:DataProvider — when null the edges of the graph are considered to have equal cost. Otherwise it must provide a non-negative double value (its cost) for every edge.
|
degreeCentrality | () | method |
public static function degreeCentrality(graph:Graph, centrality:NodeMap, considerInEdges:Boolean, considerOutEdges:Boolean):void
Computes the degree centrality for the nodes of a graph. Degree centrality measures in-, out- or overall degree of a node.
Complexity O(graph.N())
Precondition at least one of the flags considerInEdges and considerOutEdges must be true.
Parameters
graph:Graph — the input graph.
| |
centrality:NodeMap — return value. A map which provides the degree centrality as double value for every node.
| |
considerInEdges:Boolean | |
considerOutEdges:Boolean |
edgeBetweenness | () | method |
public static function edgeBetweenness(graph:Graph, centrality:EdgeMap, directed:Boolean, edgeCosts:DataProvider):void
Computes betweenness centrality for each edge of a given graph. Like nodeBetweenness() but applied to edges.
Precondition EdgeMap centrality with values initially zero
Parameters
graph:Graph | |
centrality:EdgeMap — return value. A EdgeMap which will hold a non-negative centrality value of type double for each edge.
| |
directed:Boolean | |
edgeCosts:DataProvider |
See also
getClass | () | method |
override public function getClass():Class
ReturnsClass |
graphCentrality | () | method |
public static function graphCentrality(graph:Graph, centrality:NodeMap, directed:Boolean, edgeCosts:DataProvider):void
Computes the graph centrality for the nodes of a graph. Graph centrality is defined as the reciprocal of the maximum of all shortest path distances from a node to all other nodes in the graph. Nodes with high graph centrality have short distances to all other nodes in the graph. Also note, that for unconnected graphs the centrality values of all nodes will be zero, since the distance to some nodes is infinite.
Complexity O(graph.N()^2 + graph.N()*graph.E()) for unweighted graphs, O( (graph.N()*graph.E()) + graph.N()^2 *log(graph.N())) or: O(graph.N()) * O(Uniform) for unweighted, O(allPairs) for weighted graphs
Parameters
graph:Graph — the input graph.
| |
centrality:NodeMap — return value. A map which hold the centrality value of type double for every node.
| |
directed:Boolean — whether to consider the edges of the graph as directed or undirected.
| |
edgeCosts:DataProvider — when null the edges of the graph are considered to have equal cost. Otherwise it must provide a non-negative double value (its cost) for every edge.
|
initCentrality | () | method |
protected final function initCentrality():void
newCentrality | () | method |
nodeBetweenness | () | method |
public static function nodeBetweenness(graph:Graph, centrality:NodeMap, directed:Boolean, edgeCosts:DataProvider):void
Computes betweenness centrality for each node of a given graph. Betweenness Centrality is a measure for how often a node lies on a shortest path between each pair of nodes in the graph. Removing a central node will cause many shortest paths to change.
Complexity O(graph.N()*graph.E()) for unweighted graphs, O(graph.N() * (graph.E()+graph.N()) * log(graph.N()) for weighted graphs.
Precondition NodeMap centrality with values initially zero
Parameters
graph:Graph — the input graph.
| |
centrality:NodeMap — return value. A NodeMap which will holds a non-negative centrality value of type double for each node.
| |
directed:Boolean — whether to consider the edges of the graph as directed or undirected. If false, the algorithm traverse every edge in both direction regardless of the direction of the edge.
| |
edgeCosts:DataProvider — if null the edges of the graph are considered to have equal cost. Otherwise it must provide a strictly positive double value (its cost) for every edge. Invalid values are assumed to be 1.0 .
|
nodeEdgeBetweenness | () | method |
public static function nodeEdgeBetweenness(graph:Graph, nodeCentrality:NodeMap, edgeCentrality:EdgeMap, directed:Boolean, edgeCosts:DataProvider):void
Computes betweenness centrality for each node and edge of a given graph. Like nodeBetweenness() but applied to both nodes and edges.
Precondition NodeMap nodeCentrality with values initially zero
Precondition EdgeMap edgeCentrality with values initially zero
Parameters
graph:Graph | |
nodeCentrality:NodeMap — return value. A NodeMap which will hold the centrality value of type double for every node.
| |
edgeCentrality:EdgeMap — return value. A EdgeMap which will hold the centrality value of type double for every edge.
| |
directed:Boolean | |
edgeCosts:DataProvider |
See also
normalizeEdgeMap | () | method |
public static function normalizeEdgeMap(graph:Graph, map:EdgeMap):void
Like normalizeNodeMap(), but for EdgeMap.
Precondition for each edge e: map.getDouble(e) >= 0
Parameters
graph:Graph — the input graph
| |
map:EdgeMap — return value that holds double values between zero and one.
|
See also
normalizeNodeMap | () | method |
public static function normalizeNodeMap(graph:Graph, map:NodeMap):void
This method normalizes the double
values of a node map by dividing all values by the maximum of all values (maximum norm).
Note, if the maximum value is Double.POSITIVE_INFINITY
, all values other than Double.POSITIVE_INFINITY
are set to 0
.
Precondition for each node n: map.getDouble(n) >= 0
Parameters
graph:Graph — the input graph
| |
map:NodeMap — return value that holds double values between zero and one.
|
weightCentrality | () | method |
public static function weightCentrality(graph:Graph, centrality:NodeMap, considerInEdges:Boolean, considerOutEdges:Boolean, edgeWeights:DataProvider):void
Computes the weight centrality for the nodes of a graph. Weight centrality measures the weight associated with incoming, outgoing, or all edges of a node.
Note that weight centrality degenerates to degree centrality when the edges have uniform weight. In particular, when parameter 'edgeWeights' isnull
then degreeCentrality (degreeCentrality()) is invoked instead.
Complexity O(graph.E())
Parameters
graph:Graph — The input graph.
| |
centrality:NodeMap — Return value. A map which provides the value centrality as double value for every node.
| |
considerInEdges:Boolean — Whether the weights associated with incoming edges should be considered.
| |
considerOutEdges:Boolean — Whether the weights associated with outgoing edges should be considered.
| |
edgeWeights:DataProvider — When null , the edges of the graph are considered to have uniform weight of 1.0. Otherwise it must provide a non-negative double value (the weight) for every edge.
|
See also