Computational Network Science: An Algorithmic Approach

By Henry Hexmoor

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

• Language: English
• Publisher: Elsevier Science
• Release date: Sep 23, 2014
• ISBN: 9780128011560

Henry Hexmoor

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.

Book preview

Computational Network Science

An Algorithmic Approach

Henry Hexmoor

Table of Contents

Cover

Title page

Copyright Page

Preface

Chapter 1: Ubiquity of Networks

Abstract

1.1. Introduction

1.2. Online social networking services

1.3. Online bibliographic services

1.4. Generic network models

1.5. Network model generators

1.6. A real-world network

1.7. Conclusions

Chapter 2: Network Analysis

Abstract

2.1. Conclusions and future work

Chapter 3: Network Games

Abstract

3.1. Game theory introduction

3.2. Congestion games and resource pricing

3.3. Cooperation in network synthesis game

3.4. Bayesian games

3.5. Applications

3.6. Conclusion

Chapter 4: Balance Theory

Abstract

4.1. Conclusion

Chapter 5: Network Dynamics

Abstract

5.1. Evolutionary and volatile network dynamics

5.2. Time graphs

5.3. Markov chains

5.4. Strategic network partnering using Markov decision processes

5.5. Conclusion

Chapter 6: Diffusion and Contagion

Abstract

6.1. Population preference spread

6.2. Percolation model

6.3. Disease epidemic models

6.4. Community detection

6.5. Community correlation versus influence

6.6. Conclusion

Chapter 7: Influence Diffusion and Contagion

Abstract

7.1. Stochastic model

7.2. Social learning

7.3. Social media influence

7.4. Conclusion

Chapter 8: Power in Exchange Networks

Abstract

8.1. Conclusion

Chapter 9: Economic Networks

Abstract

9.1. Network effects

9.2. Conclusion

Chapter 10: Network Capital

Abstract

10.1. Social capital used for physical capital access

10.2. Conclusion

Chapter 11: Network Organizations

Abstract

11.1. Conclusion

Chapter 12: Emerging Trends

Abstract

12.1. Conclusion

Appendix

Copyright Page

Morgan Kaufmann is an imprint of Elsevier

225 Wyman Street, Waltham, MA 02451, USA

Copyright © 2015 Elsevier Inc. All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher’s permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.

This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).

Notices

Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.

Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.

To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library.

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress.

ISBN: 978-0-12-800891-1

For information on all MK publications visit our website at http://www.mkp.com

Preface

The days of the need for gurus and extensive libraries are behind us. The Internet provides ready and rapid access to knowledge for all. This book offers necessary and sufficient descriptions of salient knowledge that have been tested in traditional classrooms. The book weaves foundations together from disparate disciplines including mathematical sociology, economics, game theory, political science, and biological networks.

Network science is a new discipline that explores phenomena common to connected populations across the natural and man-made world. From animals to commodity trades, networks provide relationships among individuals and groups. Analysis and leveraging connections provide insights and tools for persuasion. Studies in this area have largely focused on opinion attributes. The impetus for this book is a need to examine computational processes for automating tedious analyses and usage of network information for online migration. Once online, network awareness will contribute to improved public safety and superior services for all.

A collection of foundational notions for economic and social networks is available in Jackson (2008). A mathematical treatment of generic networks is present in Easly and Kleinberg (2010). A complementary gap filled by this book is an algorithmic approach. I provide a fast-paced introduction to the state of the art in network science. References are offered to seminal and contemporary developments. The book uses mathematical cogency and contemporary computational insights. It also calls to arm further research on open problems.

The reader will find a broad treatment of network science and review of key recent phenomena. Senior undergraduates and professional people in computational disciplines will find sufficient methodologies and processes for implementation and experimentation. This book can also be used as a teaching material for courses on social media and network analysis, computational social networks, and network theory and applications. Our coverage of social network analysis is limited and details are available in Golbeck (2013) and Borgatti et al. (2013).

Whereas a teacher is a tour guide to the subject matter, this book is a reference manual. Chapters in each part are related and they progress in maturity. Chapters are semi-independent and a course instructor may choose any order that meets the course objectives. Exercises at the end of each chapter are students’ hands-on projects that are designed for covering learning activities during a semester. Some code is provided in appendices for prototyping and learning purposes only. We do not provide a how-to guide to mainstream social media or codebook for application development that is available elsewhere.

Henry Hexmoor

Carbondale, IL

2014

References

Borgatti S, Everett M, Johnson J. Analyzing Social Networks. SAGE Publications; 2013.

Easly D, Kleinberg J. Networks, Crowds, and Markets. Cambridge University Press; 2010.

Golbeck J. Analyzing the Social Web. Morgan Kaufmann Publications; 2013.

Jackson M. Social and Economic Networks. Princeton University Press; 2008.

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