NETWORK SCIENCE

Committee on Network Science for Future Army Applications

Board on Army Science and Technology

Division on Engineering and Physical Sciences

NATIONAL RESEARCH COUNCIL OF THE NATIONAL ACADEMIES

THE NATIONAL ACADEMIES PRESS
Washington, D.C.
www.nap.edu



The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement



Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page R1
Network Science NETWORK SCIENCE Committee on Network Science for Future Army Applications Board on Army Science and Technology Division on Engineering and Physical Sciences NATIONAL RESEARCH COUNCIL OF THE NATIONAL ACADEMIES THE NATIONAL ACADEMIES PRESS Washington, D.C. www.nap.edu

OCR for page R1
Network Science THE NATIONAL ACADEMIES PRESS 500 Fifth Street, N.W. Washington, DC 20001 NOTICE: The project that is the subject of this report was approved by the Governing Board of the National Research Council, whose members are drawn from the councils of the National Academy of Sciences, the National Academy of Engineering, and the Institute of Medicine. The members of the committee responsible for the report were chosen for their special competences and with regard for appropriate balance. This study was supported by Contract/Grant No. DAAD19-03-D-0002, between the National Academy of Sciences and the Department of the Army. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of the organizations that provided support for the project. International Standard Book Number 0-309-10026-7 (Book) International Standard Book Number 0-309-65388-6 (PDF) Library of Congress Control Number 2005936575 Additional copies of this report are available from the National Academies Press, 500 Fifth Street, N.W., Lockbox 285, Washington, DC 20055; (800) 624-6242 or (202) 334-3313 (in the Washington metropolitan area); Internet, http://www.nap.edu. Copyright 2005 by the National Academy of Sciences. All rights reserved. Printed in the United States of America

OCR for page R1
Network Science THE NATIONAL ACADEMIES Advisers to the Nation on Science, Engineering, and Medicine The National Academy of Sciences is a private, nonprofit, self-perpetuating society of distinguished scholars engaged in scientific and engineering research, dedicated to the furtherance of science and technology and to their use for the general welfare. Upon the authority of the charter granted to it by the Congress in 1863, the Academy has a mandate that requires it to advise the federal government on scientific and technical matters. Dr. Ralph J. Cicerone is president of the National Academy of Sciences. The National Academy of Engineering was established in 1964, under the charter of the National Academy of Sciences, as a parallel organization of outstanding engineers. It is autonomous in its administration and in the selection of its members, sharing with the National Academy of Sciences the responsibility for advising the federal government. The National Academy of Engineering also sponsors engineering programs aimed at meeting national needs, encourages education and research, and recognizes the superior achievements of engineers. Dr. Wm. A. Wulf is president of the National Academy of Engineering. The Institute of Medicine was established in 1970 by the National Academy of Sciences to secure the services of eminent members of appropriate professions in the examination of policy matters pertaining to the health of the public. The Institute acts under the responsibility given to the National Academy of Sciences by its congressional charter to be an adviser to the federal government and, upon its own initiative, to identify issues of medical care, research, and education. Dr. Harvey V. Fineberg is president of the Institute of Medicine. The National Research Council was organized by the National Academy of Sciences in 1916 to associate the broad community of science and technology with the Academy’s purposes of furthering knowledge and advising the federal government. Functioning in accordance with general policies determined by the Academy, the Council has become the principal operating agency of both the National Academy of Sciences and the National Academy of Engineering in providing services to the government, the public, and the scientific and engineering communities. The Council is administered jointly by both Academies and the Institute of Medicine. Dr. Ralph J. Cicerone and Dr. Wm. A. Wulf are chair and vice chair, respectively, of the National Research Council. www.national-academies.org

OCR for page R1
Network Science COMMITTEE ON NETWORK SCIENCE FOR FUTURE ARMY APPLICATIONS CHARLES B. DUKE, Chair, Xerox Innovation Group, Webster, New York JOHN E. HOPCROFT, Vice Chair, Cornell University, Ithaca, New York ADAM P. ARKIN, Lawrence Berkeley National Laboratory, Berkeley, California ROBERT E. ARMSTRONG, National Defense University, Washington, D.C. ALBERT-LASZLO BARABASI, University of Notre Dame, Notre Dame, Indiana RONALD J. BRACHMAN, Defense Advanced Research Projects Agency, Arlington, Virginia NORVAL L. BROOME, MITRE Corporation (retired), Suffolk, Virginia STAN DAVIS, Brookline, Massachusetts RICHARD A. De MILLO, Georgia Institute of Technology, Atlanta WILLIAM J. HILSMAN, Institute for Defense Analyses, Philadelphia, Pennsylvania WILL E. LELAND, Telcordia Technologies, Inc., Piscataway, New Jersey THOMAS W. MALONE, Massachusetts Institute of Technology, Cambridge RICHARD M. MURRAY, California Institute of Technology, Pasadena JACK PELLICCI, Oracle Public Sector, Reston, Virginia PAMELA A. SILVER, Harvard Medical School, Boston, Massachusetts PAUL K. VAN RIPER, LTG, United States Marine Corps (retired), Williamsburg, Virginia DUNCAN J. WATTS, Columbia University, New York Staff ROBERT J. LOVE, Study Director NIA D. JOHNSON, Research Associate TOMEKA N. GILBERT, Senior Program Assistant (until May 23, 2005) LEON A. JAMES, Senior Program Assistant (after May 23, 2005)

OCR for page R1
Network Science BOARD ON ARMY SCIENCE AND TECHNOLOGY JOHN E. MILLER, Chair, L3 Communications Corporation, Reston, Virginia HENRY J. HATCH, Vice Chair, Army Chief of Engineers (retired), Oakton, Virginia SETH BONDER, The Bonder Group, Ann Arbor, Michigan JOSEPH V. BRADDOCK, The Potomac Foundation, McLean, Virginia NORVAL L. BROOME, MITRE Corporation (retired), Suffolk, Virginia ROBERT L. CATTOI, Rockwell International (retired), Dallas, Texas DARRELL W. COLLIER, U.S. Army Space and Missile Defense Command (retired), Leander, Texas ALAN H. EPSTEIN, Massachusetts Institute of Technology, Cambridge ROBERT R. EVERETT, MITRE Corporation (retired), New Seabury, Massachusetts PATRICK F. FLYNN, Cummins Engine Company, Inc. (retired), Columbus, Indiana WILLIAM R. GRAHAM, National Security Research, Inc., Arlington, Virginia PETER F. GREEN, University of Michigan, Ann Arbor EDWARD J. HAUG, University of Iowa, Iowa City M. FREDERICK HAWTHORNE, University of California, Los Angeles CLARENCE W. KITCHENS, Science Applications International Corporation, Vienna, Virginia ROGER A. KRONE, Boeing Integrated Defense Systems, Philadelphia, Pennsylvania JOHN W. LYONS, U.S. Army Research Laboratory (retired), Ellicott City, Maryland MALCOLM R. O’NEILL, Lockheed Martin Corporation, Bethesda, Maryland EDWARD K. REEDY, Georgia Tech Research Institute (retired), Atlanta DENNIS J. REIMER, DFI International, Washington, D.C. WALTER D. SINCOSKIE, Telcordia Technologies, Inc., Piscataway, New Jersey JUDITH L. SWAIN, University of California, San Diego WILLIAM R. SWARTOUT, Institute for Creative Technologies, Marina del Rey, California EDWIN L. THOMAS, Massachusetts Institute of Technology, Cambridge BARRY M. TROST, Stanford University, Stanford, California Staff BRUCE A. BRAUN, Director WILLIAM E. CAMPBELL, Manager, Program Operations CHRIS JONES, Financial Associate ROBERT J. LOVE, Senior Program Officer MARGARET NOVACK, Senior Program Officer HARRISON T. PANNELLA, Senior Program Officer DONALD L. SIEBENALER, Senior Program Officer DEANNA P. SPARGER, Program Administrative Coordinator

OCR for page R1
Network Science This page intentionally left blank.

OCR for page R1
Network Science Preface This study was an exercise in coping with complexity. The subject matter is complex. Important networks like the Internet and the power grid are becoming ever larger, encompassing up to hundreds of millions if not billions of nodes. They exhibit complex and often dynamic patterns of links between the nodes. Networks interact with one another and are recursive. Social networks are built upon information networks which are built upon communications networks which in turn are built on physical networks. Moreover, this layered structure of interacting networks built on top of other networks is reflected directly in the diversity of communities that study networks: sociologists, management theorists, warfare strategists, economists, biologists, chemists, physicists, and a wide variety of engineers. Getting such a diverse group to agree on a common core of knowledge about networks, i.e., the content of network science, is a significant challenge. Last but by no means least, the customer community for this study is equally diverse. Military planners and strategists, operational commanders (“warfighters”), logistics commanders, and R&D managers each have their own points of view on what network science ought to provide in order to be useful to the military. The extent to which the committee did manage to cope successfully with these complexities will be judged by you, the reader. In order to comprehend the topical scope, committee members were selected who are actively publishing experts on physical, biological, engineered, and social networks. Systematic efforts at outreach to interested communities were undertaken, including a survey of extant courses on networks and a questionnaire sent to members of as diverse a group of communities as the committee could identify. Committee members also were selected to encompass various constituencies in the military that have an interest in the design, procurement, deployment, and use of networks. Representatives of each of these groups made presentations to the committee. Value creation scenarios were prepared to address the concerns of these constituencies. Thus, the composition of the committee, the data that it collected, and the analyses that it generated are broadly representative of the inherent complexities of the subject of the study. The committee was able to lay out the scope of the topic, organize an overview of the diverse streams of activity and knowledge into a synthetic whole, and survey the sorts of options that the Army might want to explore to create value from investments in network science. As a result, it is my hope that this report will broaden the horizons of its readers, stimulate them to think about the role of network science in today’s connected world, and, hopefully, act upon their enhanced understanding of this role. The committee learned three major things of overarching importance about the role of networks in modern society and the availability of the knowledge necessary to create and operate them. First, networks lie at the core of the economic, political, and social fabric of the 21st century. The demand for structured knowledge that can be used to design, procure, and operate networks is ubiquitous and growing rapidly. Moreover, social and communications networks lie at the core of both conventional military operations and the war on terrorism. Thus, investment in network science is both a strategic and urgent national priority. Second, the current state of knowledge about the structure, dynamics, and behaviors of both large infrastructure networks and vital social networks at all scales is primitive. A lot is known about the design, construction, and use of the components of physical networks. The science of integrating these components into large, complex, interacting networks that are robust and whose behaviors are predictable is uncharted ground. Communications networks that are being built today exhibit unpredictable behavior and robustness. For social networks, even the characteristics of the components are largely unexplored. The development of predictive models of the behavior of large complex networks is difficult. It is basically an unsolved problem that will require focused attention from the best brains in the nation to make significant progress on it.

OCR for page R1
Network Science Third, the United States is not on track to consolidate the information that already exists about the science of large, complex networks, much less to develop the knowledge that will be needed to design the networks envisaged by the military to realize futuristic warfare concepts like network-centric operations. Current research on networks is highly fragmented, usually conducted in disciplinary settings. The committee did observe an encouraging preliminary consensus on the part of practitioners about the broad outlines of the core of knowledge that allows them to practice their art in a wide variety of applications areas. Nevertheless, individual researchers are naturally more interested in marketing their own work than in collaborating on larger projects of the scope that would have a realistic chance to impact the Army’s aspirations. Major changes in the funding and organization of activities on network science are required before the knowledge that can realistically be expected from research in this area will be available in a form that is useful for the design and procurement of the capabilities envisaged by the Army. The committee does not expect its report to change any of these things. It does, however, aspire to articulate its learnings clearly and to document the data and analysis on which they are based. It also aspires to provide specific answers to the questions in the statement of task. I hope that the readers will find that these aspirations were accomplished. Charles B. Duke, Chair Committee on Network Science for Future Army Applications

OCR for page R1
Network Science Acknowledgments The committee thanks the organizations and guest speakers that provided support. The presentations from the military on network-centric operations (NCO), on the procurement and deployment of operational capabilities of NCO in the field, and on the Army’s R&D portfolio of network-related research were especially helpful. The committee also thanks the various academic and military researchers with whom it conducted personal interviews over the telephone. Their candid comments were instrumental in the committee’s achieving a realistic understanding of the complexities of current research on networks. The committee is deeply grateful to Katy Börner of Indiana University for her analysis of the data acquired from our outreach questionnaire and her permission to use this material in its report. The excellent support of the National Research Council staff is especially appreciated. Special thanks go to Bob Love, who worked closely with the chair and vice chair during the entire study process. The cheerful and effective assistance of Tomeka Gilbert, Nia Johnson, Deborah Kuzmanovic, and Leon James was indispensable to accomplishing this study.

OCR for page R1
Network Science Acknowledgment of Reviewers This report has been reviewed in draft form by individuals chosen for their diverse perspectives and technical expertise, in accordance with procedures approved by the NRC Report Review Committee. The purpose of this independent review is to provide candid and critical comments that will assist the institution in making its published report as sound as possible and to ensure that the report meets institutional standards for objectivity, evidence, and responsiveness to the study charge. The review comments and draft manuscript remain confidential to protect the integrity of the deliberative process. We wish to thank the following individuals for their review of this report: Anthony Ephremides, University of Maryland, Gerald J. Iafrate, North Carolina State University, Leonard Kleinrock, NAE, University of California, Los Angeles, Scott E. Page, University of Michigan, Lawrence G. Roberts, NAE, Anagran, Inc., Alan B. Salisbury, U.S. Army (retired), and Judith L. Swain, IOM, University of California, San Diego. Although the reviewers listed above have provided many constructive comments and suggestions, they were not asked to endorse the conclusions or recommendations nor did they see the final draft of the report before its release. The review of this report was overseen by Stewart D. Personick, NAE, Drexel University. Appointed by the National Research Council, he was responsible for making certain that an independent examination of this report was carried out in accordance with institutional procedures and that all review comments were carefully considered. Responsibility for the final content of this report rests entirely with the authoring committee and the institution.

OCR for page R1
Network Science Contents     EXECUTIVE SUMMARY   1 1   INTRODUCTION   7      Scope of the Study,   8      Study Approach and Constraints,   8      Report Organization,   9      References,   10 2   NETWORKS AND NETWORK RESEARCH IN THE 21ST CENTURY   11      References,   18 3   NETWORKS AND THE MILITARY   19      Networks and the Army,   19      Network-Centric Warfare and Network-Centric Operations,   19      Challenges,   22      Optimizing Warfighting Organizations,   22      Network Research of Special Interest to the Military,   24      References,   25 4   THE DEFINITION AND PROMISE OF NETWORK SCIENCE   26      What Is Network Science?,   26      Positioning of Network Science,   28      References,   29 5   THE CONTENT OF NETWORK SCIENCE   30      How Do We Know?,   30      Content,   30      References,   32 6   STATUS AND CHALLENGES OF NETWORK SCIENCE   33      Key Messages,   33      Questionnaire Process,   33      The Respondents,   33      Dissenting Voices,   34      Defining the Field,   34      Attributes of a Network,   34      Derived Properties of Networks,   35      Future Evolution of the Definition of Network Science,   36

OCR for page R1
Network Science      Research Challenges,   36      The Social Structure of Network Science,   37      Reference,   38 7   CREATING VALUE FROM NETWORK SCIENCE: SCOPE OF THE OPPORTUNITY   39      Creating Economic Value from Research Knowledge,   39      Scenarios for Value Creation,   39      Scenario 1, Building the Base,   39      Scenario 2, Next-Generation R&D,   40      Scenario 3, Creating a Robust Network-centric Warfare/Operations Capability,   41      Implication of the Scenarios,   42      Findings from Scenario 1,   42      Findings from Scenarios 2 and 3,   44      References,   45 8   CONCLUSIONS AND RECOMMENDATIONS   46      Overarching Conclusions,   46      Specific Conclusions,   48      Recommendations,   49     APPENDIXES         A  BIOGRAPHICAL SKETCHES OF COMMITTEE MEMBERS   55     B  COMMITTEE MEETINGS AND OTHER ACTIVITIES   58     C  CONTENT OF NETWORK SCIENCE COURSES   60     D  QUESTIONNAIRE DATA   65     E  OPPORTUNITIES FOR CREATING VALUE FROM NETWORK SCIENCE   93     F  RECOMMENDED READING LIST   107

OCR for page R1
Network Science Figures, Tables, and Boxes FIGURES 2-1   Number of papers with the term “complex network” in the title,   15 2-2   Magazines and journals with articles on networks,   16 3-2-1   Representative activities and networks involved in responses to a bioterrorist attack,   23 6-1   Reasons for saying there is no field of network science,   35 6-2   Share of responses that mention an attribute,   35 6-3   Responses identifying driving applications,   36 6-4   Major research challenges,   36 6-5   Relationships among invitees, respondents, and collaborators,   37 6-6   Network science researchers network,   37 D-1   New names by response ID,   72 D-2   Countries where respondents were located,   73 D-3   States where respondents were located,   75 D-4   Fields selected by respondents,   77 D-5   Most frequently mentioned fields,   78 D-6   Reasons for saying there is no field of network science,   79 D-7   Responses identifying network attributes,   80 D-8   Derived properties of networks mentioned by respondents,   81 D-9   Driving applications identified by respondents,   84 D-10   Number of responses to driving applications question,   84 D-11   Major research challenges,   86 D-2-1   Relationships among invitees, respondents, and collaborators,   88 D-2-2   Network science researchers network,   89 D-2-3   Researchers with high BC values and low BC values,   90 D-2-4   Largest component of the NSRN,   91 D-2-5   Disciplinary heterogeneity of the NSRN,   92 E-1   Schematic depiction of next-generation model for Army R&D showing the relationship between the main entities in this model,   99

OCR for page R1
Network Science TABLES ES-1   Network Research Areas,   5 2-1   Representative Networks,   12 2-2   Maturity, Structure, Characteristics, and Impacts of Some Networks,   13 3-1   Network Research Areas,   24 8-1   Network Research Areas,   50 C-1   Representative List of Courses on Computer Science,   61 C-2   Real-World Networks Appearing in Courses,   62 C-3   Content of a Typical Network Science Course,   62 C-4   Network Models Commonly Used to Generate Network Topologies and Analytical Tools Used to Characterize and Study the Properties of Models,   63 D-1   Respondent’s Country,   74 D-2   Canadian Respondent Provinces,   74 D-3   Respondent States,   76 D-4   Responses Per Field,   77 D-5   Respondent Affiliations,   78 D-6   Is Your Work Potentially Part of an Emerging Field of Network Science?,   78 D-7   Is There an Identifiable Field of Network Science?,   79 D-8   Summary Decomposition of the Input Attributes of Networks,   80 D-9   Summary Decomposition of the Derived Properties of Networks,   82 D-10   Summary Decomposition of Constraint Models,   83 D-11   Summary Decomposition of the Problem Dimensions of Networks,   83 D-12   Major Players and Cited Applications,   85 D-2-1   Researchers Who Are Frequently Mentioned and Listed as Collaborators,   88 D-2-2   Researchers Who Act as Gatekeepers,   89 D-2-3   Components in the NSRN,   90 BOXES ES-1   Summary of Responses to the Statement of Task,   2 1-1   Network Science: Foundation of Our Connected Age,   8 1-2   Statement of Task,   8 2-1   Books Relevant to Network Science,   17 3-1   Case Studies in Net-centric Operations,   21 3-2   Dependence of Army Operations on Networks: An Example,   23 8-1   Summary of Responses to the Statement of Task,   47 D-1   NRC Network Science Survey,   66 D-2   Mapping the Social Network and Expertise of Network Science Researchers,   88 E-1   Case Study from the World Health Organization: Avian Influenza,   103

OCR for page R1
Network Science Acronyms and Abbreviations AAAS American Association for the Advancement of Science AIDS acquired immunodeficiency syndrome APS American Physical Society BAST Board on Army Science and Technology BCT brigade combat team BFT Blue Force Tracker C3 command, control, and communications C4ISR command, control, communications, computers, intelligence, surveillance, and reconnaissance CDC Centers for Disease Control COP common operational picture DARPA Defense Advanced Research Projects Agency DOD Department of Defense DOE Department of Energy FBCB2 Force XXI Battle Command Brigade and Below FCS Future Combat System GIG Global Information Grid HIV human immunodeficiency virus IED improvised explosive device JCI Joint Combat Identification JNN Joint Network Nodes JTF Joint Task Force MAS medical aid station NAS National Academy of Sciences NASA National Aeronautics and Space Administration NCE Networked Center of Excellence NCO network-centric operations NCW network-centric warfare

OCR for page R1
Network Science NIH National Institutes of Health NRC National Research Council NSF National Science Foundation NSRN network science researcher network NTC National Training Center OCP Open Control Platform OFT Office of Force Transformation OPFOR opposing force OSI open system interconnection PI principal investigator R&D research and development RFP Request for Proposal S&T science and technology SARS severe acute respiratory syndrome SBIR Small Business Innovation Research SEC Software-Enabled Control SIAM Society for Industrial and Applied Mathematics TCP/IP Transmission Control Protocol/Internet Protocol UAV unmanned aerial vehicle UGC unmanned ground vehicle URL Uniform Resource Locator WHO World Health Organization www World Wide Web