User:ErikaDomotor/Connectivity measures (network)

Connectivity measures (network)

Connectivity measures are quantitative attributes of network structures referring to their complexity and connectedness. These measures are extremely useful to analyze properties of transportation networks, such as road networks or Air Transport Networks, and many other geographical and spatial networks. In graph theory connectivity is defined as an absolute property, however in terms of larger systems it makes sense to define scaled measures of this attribute. Complex networks are generally described by their nodes and edges but several other measures may be used to characterize the underlying structure. Such useful characteristics are the diameter, the ratio of links and nodes and the number of cycles. These are all examples to connectivity measures.

Examples of connectivity measures

• Diameter is the simplest connectivity measure of a network. By definition, it is the longest shortest path between any two nodes of a graph. A smaller diameter refers to a more dense and therefore more complex and connected network.

• Nearest neighbor measures are commonly used to characterize in spatial networks or any other networks with weighted links or nodes. The simplest nearest neighbor measure are properties of a certain node, rather than a network. To describe a whole system, different types of averages can be defined. In spatial networks a simple nearest neighbor measure of a node is a function of the area occupied by the node, the area occupied by a neighbor of the node and the distance between the two neighbors. A basic realization of this type of measure is the distance between two linked nodes. A node is more connected to the network if the nearest neighbor measure is lower.

• Link-node ratio (Beta index) is a connectivity measure calculated as the ratio of the number of edges to number of vertices. If the beta index is higher, the network is more connected and more complex.

• Alpha index is a measure which reflects the relative number of cycles compared to the maximum possible number of cycles in the network. The higher the alpha index, the more a network is connected. The formula for alpha index is

${\tfrac {e-v}{v(v-1)/2-(v-1)}}$

where $e$ is the number of edges (links) and $v$ is the number of vertices (nodes).

• Gamma index is the ratio of the number of links to the maximum possible number of links. The higher the gamma index, the more a network is connected. The formula for gamma index is

${\tfrac {e}{v(v-1)/2}}$

where $e$ is the number of edges (links) and $v$ is the number of vertices (nodes).

Applications of connectivity measures

• Connectivity measures are commonly used to analyze transportation networks. A specific example is to characterize the structure of air transport network. In these networks nodes are airports or cities and links are the routes between them. Connectivity measures reflects the accessibility of the cities. A major change in the industry, such as the merger of two airline companies, modifies the attributes of the network. Such structural changes are well described by connectivity measures.

• Another application from the field of transportation is the investigation to road network structures. An example is the characterization of of bicycle and walking paths in a city. Connectivity and density of roads available for pedestrians and bikers are important indicators of a good neighborhood. These attributes of a neighborhood can be described for example by nearest neighbor measures.

• Connectivity measures are widely used in spatial ecology. In ecological networks nodes are species and links between them are defined on a spatial basis. Connectivity, or its opposite isolation is a fundamental factor of the distribution of species. To characterize complexity and connectedness the nearest neighbor measures are most commonly applied in this field.

• Basic connectivity measures are applied to analyze the structure of neuro-networks of the brain. Easily computable measures, such as link-node ratio and average nearest neighbor degree aims to describe neurobiologically meaningful question. Such application is to detect functional integration and segregation of the brain.

See also

• Connectivity (graph theory)
• Metrics (networking)
• Complex networks
• Network Science

External links

• http://www.barabasilab.com/