Computational Network Science

An Algorithmic Approach

Henry Hexmoor

• Publisher: Morgan Kaufmann
• Year: 2014
• ISBN:
  9780128011560
• Topic: Computer Science
• Subtopic: Computer Networking
• Index: Computer Science

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

Chapter 1

Ubiquity of Networks

Abstract

We begin this chapter with an outline of underlying concepts and types of networks. Next, networks of people on popular social media such as Facebook are reviewed for social networking among people. Whereas networking relies on making and maintaining relationship networks, this book focuses on the science of all types of networks including human networking networks. There are static networks such as pixels on a digital image. States on a US map or a subway station map are man-made stationary networks. There are tangible, dynamic networks such as vehicles on roadways. There are intangible, implicit relationship networks in daily lives of people who may share similarity. A taxonomy puts networks in sharper focus. We then introduce the most popular mathematical models of artificial networks and algorithms for generating them. This is followed by an example of a real-world package delivery network. The chapter ends with a few student exercises. This chapter provides rudimentary concepts for understanding subsequent chapters.

Keywords

networks

social networks

mathematical network models

network generation algorithms

1.1. Introduction

Broadly speaking, a network is a collection of individuals (i.e., nodes) where there are implicit or explicit relationships among individuals in a group. The relationships may be strictly physical as in some sort of physical formation (e.g., pixels of a digital image or cars on the road), or they may be conceptual such as friendship or some similarity among pairs or within a pair. In an implicit network, individuals are unaware of their relationships, whereas in an explicit network, individuals are familiar with at least their local neighbors. In certain implicit networks called affinity networks, there is a potential for explicit connections from relationships that account for projected connection such as homophilly (i.e., similarity) (McPherson et al., 2001). Biological networks capture relationships among biological organisms. For instance, the human brain neurons form a large network called a connectome (Seung, 2012). An ant society is an example of a large biological network (Moffett, 2010). There are many examples of small-scale animal networks, including predators and their prey, plant diseases, and bird migration. Human crowds and network organizations (e.g., government or state agencies, honey grids in bee colonies) are other examples of natural networks. Modern anonymous human networks have capacities for crowd solving problems (Nielsen, 2012), where a group of independently minded individuals possess a collective wisdom that is available to singletons (Reingold, 2000). Social and political networks model human relationships, where social and political relations are paramount. Economic networks are models of parties related to economic relationships such as those among buyers (and consumers), sellers (and producers), and intermediaries (i.e., traders and brokers) (Jackson, 2003). Beyond natural networks, there are myriads of synthetic networks. The grid of a photograph is an example of synthetic networks. Nanonetworks are attempts to network nanomachines for emerging nanoscale applications (Jornet and Pierobon, 2011). A large class of networks is a complex engineered network (CEN) that is a man-made network, where the topology is completely neither regular nor random. A CEN supports evolving functionalities. Examples of CENs are the Internet, wireless networks, power grids with smart homes and cars, remote monitoring networks with satellites, global networks of telescopes, and networks of instruments and sensors from battlefields to hospitals. Time requirements in CENs range from seconds in cyber-attacks to years in greenhouse gas emissions. Data and control flow in CENs must be managed over connections that could span thousands of miles.

A few synthetic network categories, including CENs, are created intentionally. Here, we list six types:

1. Social networks through networking sites and services

2. Political networks as in parliamentary cabinets and political committees

3. Computer networks that include computers as nodes and how they communicate over local, wide area, and wireless links (e.g., sensor networks)

4. Telecommunication networks as in switches for nodes and respective routing paths

5. Power grids

6. Cellular networks as in cellular base stations and transmission frequencies

There are many synthetic, however, unintended, network categories. For example, colocated brick-and-mortar businesses may share clientele that is sometimes unintended. As such, those businesses form a location affinity network. Relationships in affinity networks are only implied and in the context of the affinity context (e.g., colo...

Table of contents

• Cover
• Title page
• Table of Contents
• Copyright Page
• Preface
• Chapter 1: Ubiquity of Networks
• Chapter 2: Network Analysis
• Chapter 3: Network Games
• Chapter 4: Balance Theory
• Chapter 5: Network Dynamics
• Chapter 6: Diffusion and Contagion
• Chapter 7: Influence Diffusion and Contagion
• Chapter 8: Power in Exchange Networks
• Chapter 9: Economic Networks
• Chapter 10: Network Capital
• Chapter 11: Network Organizations
• Chapter 12: Emerging Trends
• Appendix