Terminology


Basic Network Terminology
  • Vertex - A vertex is simply drawn as a node or a dot.
  • Edge - An edge (a set of two elements) is drawn as a line connecting two vertices, called endpoints or end vertices or end vertices. 
    • Directed Edge - A directed edge is an ordered pair of nodes that can be represented graphically as an arrow drawn between the nodes.
    • Undirected Edge - An undirected edge disregards any sense of direction and treats both nodes interchangeably.
  • Node Degree - The degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.
    • Out Degree - The number of edges leaving a vertex.
    • In Degree - The number of edges entering a vertex.
  • SizeThe size of a graph is the number of its edges.
  • Weight - A weighted graph associates a label (weight) with every edge in the graph. Weights are usually real numbers. The weight of an edge is often referred to as the "cost" of the edge. In applications, the weight may be a measure of the length of a route, the capacity of a line, the energy required to move between locations along a route, etc. 

Network Overview

  • Average Degree - Average number of links per node.
  • Average Weighted Degree - Average of sum of weights of the edges of nodes.
  • DistanceThe distance between two nodes is defined as the number of edges along the shortest path connecting them.
  • Average Distance - The Average of distance between all pairs of nodes.
  • Network Diameter - The maximum distance between any pair of nodes in the graph.
  • Modularity - Modularity is one measure of the structure of networks or graphs. It was designed to measure the strength of division of a network into modules (also called groups, clusters or communities). Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules.
  • Connected Components - a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

Node Overview

  • Clustering Coefficient - a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together.
  • Centrality - centrality refers to indicators which identify the most important vertices within a graph. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, and super spreaders of disease.
    • Closeness Centrality - In connected graphs there is a natural distance metric between all pairs of nodes, defined by the length of their shortest paths. The farness of a node is defined as the sum of its distances to all other nodes, and its closeness is defined as the reciprocal of the farness. Thus, the more central a node is the lower its total distance to all other nodes.
    • Betweenness Centrality - Betweenness is a centrality measure of a vertex within a graph (there is also edge betweenness, which is not discussed here). Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes.
    • Eigenvector Centrality - Eigenvector centrality is a measure of the influence of a node in a network. It assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.

Edge Overview

  • Average Path Length - Average path length is defined as the average number of steps along the shortest paths for all possible pairs of network nodes. It is a measure of the efficiency of information or mass transport on a network.

Comments