Hexmoor Computational Network Science

An Algorithmic Approach
1. Auflage 2014
ISBN: 978-0-12-801156-0
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 128 Seiten

Reihe: Computer Science Reviews and Trends

The emerging field of network science represents a new style of research that can unify such traditionally-diverse fields as sociology, economics, physics, biology, and computer science. It is a powerful tool in analyzing both natural and man-made systems, using the relationships between players within these networks and between the networks themselves to gain insight into the nature of each field. Until now, studies in network science have been focused on particular relationships that require varied and sometimes-incompatible datasets, which has kept it from being a truly universal discipline. Computational Network Science seeks to unify the methods used to analyze these diverse fields. This book provides an introduction to the field of Network Science and provides the groundwork for a computational, algorithm-based approach to network and system analysis in a new and important way. This new approach would remove the need for tedious human-based analysis of different datasets and help researchers spend more time on the qualitative aspects of network science research. - Demystifies media hype regarding Network Science and serves as a fast-paced introduction to state-of-the-art concepts and systems related to network science - Comprehensive coverage of Network Science algorithms, methodologies, and common problems - Includes references to formative and updated developments in the field - Coverage spans mathematical sociology, economics, political science, and biological networks

Henry Hexmoor, received an M.S. from Georgia Tech and a Ph.D. in Computer Science from the State University of New York, Buffalo in 1996. He is a long-time IEEE senior member and has taught at the University of North Carolina and the University of Arkansas. Currently, he is an associate professor with the Computer Science department at Southern Illinois University in Carbondale, IL. He has published widely in the fields of artificial intelligence and multiagent systems. His research interests include multiagent systems, artificial intelligence, cognitive science, mobile robotics, and predictive models for transportation systems.

Autoren/Hrsg.

Hexmoor, Henry

Leseproben

Chapter 2

Network Analysis

Abstract

Interesting measures and properties of networks are covered under the topic of network analysis, which is adapted from the discipline of mathematical sociology beginning in the 1940s with sociologists studying networks of relationships among people in sociograms. This has yielded a standard set of measures for social network analysis that is succinctly captured in this chapter. Network analysis is gaining new enthusiasts beyond sociology in disparate disciplines such as marketing, consumption analysis, and studies of organizational dynamics. Organizational dynamics measures are nascent stages with much promise for discovering strengths and weaknesses of beneficent and productive organizations to not so well-intentioned organizations. A few suggested exercises are provided.

Keywords

social network analysis

network metrics

mathematical sociology

centrality measures

There has been a long tradition of measuring qualities for network locations from both egocentric and global perspectives. This is largely addressed with quantification attempts in mathematical sociology under the theme of social network analysis (SNA) (Wasserman and Faust, 1994; Knoke and Yang, 2007; Golbeck, 2013; Borgatti et al. 2013). There are also several popular software toolkits that perform analysis and visualization of social networks (i.e., sociograms) including UCINET and NodeXL. Tom Snijders’ SIENA is a program for the statistical analysis of network data. The NSF-sponsored visualization project is Traces (Suthers, 2011), which traces out the movements, confluences, and transformations of people and ideas in online social networks.

The aim of this chapter is to review a selective subset of SNA measures that complement algorithmic descriptions explained in the remainder of this book. For a glossary of SNA terms, readers are recommended to consult Golbeck (2013).

We will start with egocentric (i.e., node view) measures. A degree-1 network of a node is the node and its immediate neighbor nodes. A degree-1.5 network of a node is the node’s degree-1 network and its links among immediate neighbors (Golbeck, 2013). A degree-2 network of a node is the node’s degree-1 network and all its immediate neighbors’ connections (Golbeck, 2013). A degree-n network of a node is the degree-1 network of the node plus all the nodes and the corresponding links that are no more than n links away from the starting node.

A path is a chain (i.e., succession) of nodes connected by links between pairs of nodes. Two nodes are connected if and only if (i.e., iff) there is a path between them. A connected component is a set of nodes with connected paths among all pairs of nodes in the set. A bridge is a link that connects two isolated connected components. A hub is a node with many connections. Reachability is whether two nodes are connected or not by way of either a direct or an indirect path of any length.

Geodesic distance, denoted by distanceij, is the number of links in the shortest possible path from node i to node j. Diameter of a network is the largest geodesic distance in the connected network. Reverse distance, denoted by RDij, is distanceij - (1 + Diameter). Metrics in Equations 2.1 and 2.2 are adapted from Valente and Foreman (1998):

(k)=?j?kRDjkn-1

(2.1)

(k)=?j?kRDkjn-1

(2.2)

Structural centrality measures of a node are a host of measures reflecting the structural properties of the links surrounding a focal node. For example, degree centrality of a node is the number of edges incident on the node. Closeness centrality of a node is the average of the shortest path lengths from the node to all other nodes in the network. It is a rather small number in small-world networks (Watts and Strogatz, 1998). Betweenness centrality of a node is a measure of the node’s importance (and possibly influence as discussed in Chapter 7) and is computed using the algorithm shown in Figure 2.1.

Fig. 2.1 Betweenness value computation.

Eigenvector centrality measures the centrality of neighbor nodes and has been used as a measure of influence and power, which are discussed later in this book (Bonacich and Lu, 2012). Bonacich developed a beta centrality measure CBC with a parameter a used for adjusting the importance of a node’s degree versus a parameter ß for adjusting the importance of the neighbor’s centrality. This is shown in Equation 2.3:

BC=?j?N(i)a+[ß×CBC(j)]=a logn(i)+ß×?j?N(i)CBC(j)

(2.3)

Eigenvector centrality of a node at time t is computed with Equation 2.4, where C(t) is the vector of node centralities, A is the adjacency matrix, and At is the result of iterated multiplications of A:

(t)?=At C(t)?

(2.4)

As time approaches 8, the dominant eigenvalue ? will determine the centrality vector value with the value t×V1?, where 1?, is the eigenvector corresponding to the dominant eigenvalue ? (Chiang, 2012).

Let us consider a degree-1.5 network of a node and measure the ratio of the actual number of links in that network over the total number of possible links that could exist, which yields a measure called the local clustering coefficient (Golbeck, 2013).

Density of a network is the ratio of the actual number of links in that network over the total number of possible links that could exist. Cohesion is the minimum number of edges that has to be removed before the network is disconnected.

Let us consider a cluster that is a subset of nodes s and each node may count the ratio r as node. r is the density of its neighbors in s versus the total number of its neighbors. In the set s, the node with the minimum r value rmin yields the value called density of cluster (used in Chapter 7).

Whereas centrality is a microlevel measure, centralization is a macrolevel measure, which measures variance in the distribution of centrality in a network. We show the most generic form of centralization in Figure 2.2.

Fig. 2.2 Centralization algorithm.

Leadership (L) is a measure of network domination, computed using Equation 2.5, where dmax is the degree of the node with the highest degree and di is the degree of node i (Freeman, 1978; Macindoe and Richards 2011):

=?j=1ndmax-di(n-2)×(n-1)

(2.5)

Bonding (B) measures triadic closure in a graph (Macindoe and Richards, 2011) using Equation 2.6:

=6×number of trianglesnumber of length between two paths

(2.6)

Diversity is a measure of the number of edges in a graph that are disjoint. End vertices of such edges are not adjacent (i.e., disjoint dipoles). Diversity is shown in Equation 2.7:

=number of disjoint diploes[(n/4)×((n/2)-1)]2

(2.7)

Burt’s structural holes measure gaps among connected components and as such are another measure of diversity (Burt, 1995).

2.1. Conclusions and future work

Network analysis focuses on quantification (and statistical analyses) of qualities of relative nodes’ locations as well as entire network properties. SNA has long been a stable tool for mathematical sociology (Borgatti et al., 2013). An active direction of interest has been intelligence analysis of human networks to understand, predict, and mitigate law enforcement as well as understand geopolitical landscapes. The recent debate over surveillance and monitoring of electronic communication metadata by the National Security Agency (NSA) is indicative of this fervent interest.

A second direction of interest is marketing and branding on social media. The interest is to understand human propensity for influence from network connections. Marketers use these propensities to craft viral dissemination of consumption patterns and manipulation of economic activities. The documentary filmmaker, Morgan Spurlock, has publicly explored branding on social media. His mission is to...