Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Source Title: Creativity in Load-Balance Schemes for Multi/Many-Core Heterogeneous Graph Computing: Emerging Research and Opportunities

Copyright: © 2018
|Pages: 29
DOI: 10.4018/978-1-5225-3799-1.ch002

Chapter Preview

TopNetwork Science was initiated in the late 1950’s and early 1960’s with the works of Erdös and Rényi (1959) on random graphs. However, during late 1990’s interest in complex networks exploded with the seminal works of Watts and Strogatz on small-world networks (Watts and Strogatz, 1998) and Barabási and Albert on scale-free graphs (Barabási and Albert, 1999). They showed that complex networks encode intriguing properties in their topology that reveal important details of their functional organization and the underlying real-world phenomena.

Many complex network metrics have been proposed in literature (Newman, 2003; Costa et al., 2007) to characterize the topology of complex networks.

Complex network metrics can be roughly grouped into two classes: structural and scaling metrics. On the one hand, structural metrics summarize information about the global structure of the graph, or the local organization or importance of vertices. On the other hand, the scaling of some structural metrics with the degree of vertices can reveal non-trivial high-level properties of graphs, such the scale-free form of the graph degree distribution.

Complex network metrics give information about individual elements of a graph, for example, the importance of a vertex in terms of its degree, vertex distance to other nodes, or the properties of a vertex neighborhood. Complex network metrics can also give information about the whole graph; for example, the longest shortest path distance between any two vertices (diameter), the maximum number of neighbors of any vertex, or how much the degree distribution follows a scale-free form. Finally, the scaling with the degree of some metrics, such as the clustering or the rich-club coefficient, reveals, for example, if a degree distribution follows a scale-free form or the assortativity of a graph.

Let be the adjacency matrix of a graph with vertices and edges, where:

The *degree* of a vertex is the number of nearest neighbors^{1} of . Formally, . Let be the number of vertices of degree in , such that . Let be the *degree distribution of*. denotes the fraction of vertices in a graph that have degree .

Let denote the *average degree* over all the vertices of :

A metric derived from the degree of vertices is the *maximum degree*:

Another degree metric is the average degree of the nearest neighbors of vertex , , or *neighbor degree* for short, which is defined as follows:

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved