Authored by: Elizabeth L. Ogburn , Alexander Volfovsky

Handbook of Big Data

Print publication date:  February  2016
Online publication date:  February  2016

Print ISBN: 9781482249071
eBook ISBN: 9781482249088
Adobe ISBN:


 Download Chapter



Networks are collections of objects (nodes or vertices) and pairwise relations (ties or edges) between them. Formally, a graph G is a mathematical object composed of two sets: the vertex set V = {1,…, n} lists the nodes in the graph and the edge set E = {(i, j) : ij} lists all of the pairwise connections among the nodes. Here ∼ defines the relationship between nodes. The set E can encode binary or weighted relationships and directed or undirected relationships. A common and more concise representation of a network is given by the n × n adjacency matrix A, where entry aij represents the directed relationship from object i to object j. Most often in statistics, networks are assumed to be unweighted and undirected, resulting in adjacency matrices that are symmetric and binary: aij = aji is an indicator of whether i and j share an edge. A pair of nodes is known as a dyad; a network with n nodes has ( n 2 ) distinct dyads, and in an undirected graph, this is also the total number of possible edges. The degree of a node is its number neighbors, or nodes with which it shares an edge. In a directed network, each node has an in-degree and an out-degree; in an undirected network, these are by definition the same. Some types of networks, such as family trees and street maps, have been used for centuries to efficiently represent relationships among objects (i.e., people and locations, respectively), but the genesis of the mathematical study of networks and their topology (graph theory) is usually attributed to Euler’s 1741 Seven Bridges of Königsberg (Euler, 1741).

Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.