Ted G. Lewis - Network Science Theory and Applications

Copyright 2009 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Lewis, T. G. (Theodore Gyle), 1941

Network science : theory and practice / Ted G. Lewis.

p. cm.

Includes bibliographical references and index.

ISBN 978-0-470-33188-0 (cloth)

1. Network analysis (Planning) I. Title.

T57.85.L49 2008

003 .72--dc22

2008047060

PREFACE/FOREWORD

The phrase network science may be premature, as I write this foreword, because it may be too early to declare the combination of graph theory, control theory, and cross-discipline applications a science. Indeed, many of my colleagues have presented strong arguments to the contrarydeclaring network science a fador even worsea fabrication. So it was with trepidation that in 2006 I began writing a series of essays on various aspects of scale-free networks, small worlds, and networks that self-synchronize. These rough ideas expressed by this series evolved into the book that you are now holding in your hand. Like most first attempts, it is not without flaws. Yet, writing this book was a labor of love andhopefullyit will become a useful resource for the unbiased, inquiring mind. Maybe it will establish the new science of networks as a subject taught in nearly every science, engineering, medical, and social science field of study.

Only time will tell whether this first attempt to compile what we know about the new science of networks into a single volume misses the mark or succeedsand a textbook at that! But it has always been my weakness to write on topics that are slightly ahead of their time. The risk here lies in the selection of topics that I have chosen to call network science. Clearly, one has to include the work of pioneers such as Adamic, Albert, Barabasi, Barrat, Bollobas, Erdos, Granovetter, Kephart, Lin, Liu, Mihail, Milgram, Molloy, Moore, Newman, Pastor-Satorras, Renyi, Strogatz, Tadic, Wang, Watts, Weigt, White, Zhang, and Zhu. I have done so in the first 6 of 13 chapters. These chapters develop the field from its graph theory roots, to the modern definition of a network. Entire chapters are devoted to the most famous classes: regular, random, scale-free, and small-world networks. So, the first half of this book traces the development of network science along a trail blazed by the inventors. But then what?

My second objective was to add to what is known and published by the pioneers. The risk here lies in being pretentiouspresuming to know what direction this new field might take. Once again, I relied on my weakness for being presumptuous inquisitively so. Chapter 7, Emergence, introduces new self-organizing principles for networks and shows how to custom-design networks of arbitrary degree sequence distribution; Chapter 8, Epidemics, extends the elegant work of Z. Wang, Chakrabarti, C. Wang, and Faloutsos, to the exciting new endeavor of designing antigen countermeasures for the Internet. This work can be used to explain human epidemics as well as epidemics that sweep across the Internet. Chapter 9, Synchrony, pushes the early work of Watts to new levelsclaiming that network synchronization is merely a special case of linear system stability. Simple eigenvalue tools can be used to determine the stability and synchrony of almost any linear network. Chapter 10, Influence Networks, is mostly new material and suggests what conditions must be met in order for a social network to come to consensus. As it turns out, it is not easy for groups to agree! Chapter 11, Vulnerability, builds on the PhD dissertation of Waleed Al-Mannai, who formalized and extended my own work on network risk. Al Mannais theory is being used on a daily basis to evaluate critical infrastructure systems and protect them against natural and synthetic (anthropogenic, humanmade) attacks. This has made a profound impression on the practice of homeland security. Chapter 12, Netgain, is an exploration of business modelsrelating the famous Schumpeter creative destruction process to an emergent process, and mapping the Bass and FisherPry equations onto networks. It is comforting to verify the BassFisherPry equations for networks, but furthermore, I show how these classical models may be extended to multi-product markets and oligopolies. Finally, Chapter 13, Biology, is completely on the leading edge of network science. This final chapter introduces the reader to the exciting new field of protein expression networks and suggests some new directions for the reader to consider.

The casual reader may easily skip over the mathematics, and still glean much from the application of networks to various disciplines ranging from computer science and engineering, business, public health (epidemiology), Internet virus countermeasures, social network behavior, biology, and physics. The more dedicated reader and classroom instructor may want to experiment with the software tools provided by the publisher and author (). These include 5 major Java applications: Network.jar for exploring various classes of networks and experimenting with various emergence processes; Influence.jar for the study of influence networks and social network analysis; NetworkAnalysis.jar for the study of network vulnerability and the attacker-defender network risk problem; NetGain.jar for business modeling; and BioNet.jar