World Library  
Flag as Inappropriate
Email this Article

Network science

Article Id: WHEBN0016981683
Reproduction Date:

Title: Network science  
Author: World Heritage Encyclopedia
Language: English
Subject: Social network, Netchain analysis, Complex systems, Biological network, Efficiency (Network Science)
Collection: Cybernetics, Network Theory, Networks
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Network science

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes (or vertices) and the connections between the elements or actors as links (or edges). The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."[1]

Contents

  • Background and history 1
    • Department of Defense Initiatives 1.1
  • Network properties 2
    • Density 2.1
    • Size 2.2
    • Average degree 2.3
    • Average path length 2.4
    • Diameter of a network 2.5
    • Clustering coefficient 2.6
    • Connectedness 2.7
    • Node centrality 2.8
    • Node Influence 2.9
  • Network models 3
    • Erdős–Rényi Random Graph model 3.1
    • Watts-Strogatz Small World model 3.2
    • Barabási–Albert (BA) Preferential Attachment model 3.3
  • Network analysis 4
    • Social network analysis 4.1
    • Dynamic network analysis 4.2
    • Biological network analysis 4.3
    • Link analysis 4.4
      • Network robustness 4.4.1
      • Pandemic Analysis 4.4.2
        • Susceptible to Infected 4.4.2.1
        • Infected to Recovered 4.4.2.2
        • Infectious Period 4.4.2.3
      • Web Link Analysis 4.4.3
        • PageRank 4.4.3.1
          • Random Jumping 4.4.3.1.1
    • Centrality measures 4.5
  • Spread of content in networks 5
    • The SIR Model 5.1
  • Interdependent networks 6
  • Network optimization 7
  • Network science research centers 8
  • Network analysis and visualization tools 9
  • See also 10
  • Further reading 11
  • External links 12
  • Notes 13

Background and history

The study of networks has emerged in diverse disciplines as a means of analyzing complex relational data. The earliest known paper in this field is the famous Seven Bridges of Königsberg written by Leonhard Euler in 1736. Euler's mathematical description of vertices and edges was the foundation of graph theory, a branch of mathematics that studies the properties of pairwise relations in a network structure. The field of graph theory continued to develop and found applications in chemistry (Sylvester, 1878).

Moreno's sociogram of a 1st grade class
In the 1930s Jacob Moreno, a psychologist in the Gestalt tradition, arrived in the United States. He developed the sociogram and presented it to the public in April 1933 at a convention of medical scholars. Moreno claimed that "before the advent of sociometry no one knew what the interpersonal structure of a group 'precisely' looked like (Moreno, 1953). The sociogram was a representation of the social structure of a group of elementary school students. The boys were friends of boys and the girls were friends of girls with the exception of one boy who said he liked a single girl. The feeling was not reciprocated. This network representation of social structure was found so intriguing that it was printed in The New York Times (April 3, 1933, page 17). The sociogram has found many applications and has grown into the field of social network analysis.

Probabilistic theory in network science developed as an offshoot of graph theory with Paul Erdős and Alfréd Rényi's eight famous papers on random graphs. For social networks the exponential random graph model or p* is a notational framework used to represent the probability space of a tie occurring in a social network. An alternate approach to network probability structures is the network probability matrix, which models the probability of edges occurring in a network, based on the historic presence or absence of the edge in a sample of networks.

In 1998, David Krackhardt and Kathleen Carley introduced the idea of a meta-network with the PCANS Model. They suggest that "all organizations are structured along these three domains, Individuals, Tasks, and Resources". Their paper introduced the concept that networks occur across multiple domains and that they are interrelated. This field has grown into another sub-discipline of network science called dynamic network analysis.

More recently other network science efforts have focused on mathematically describing different network topologies. Duncan Watts reconciled empirical data on networks with mathematical representation, describing the small-world network. Albert-László Barabási and Reka Albert developed the scale-free network which is a loosely defined network topology that contains hub vertices with many connections, that grow in a way to maintain a constant ratio in the number of the connections versus all other nodes. Although many networks, such as the internet, appear to maintain this aspect, other networks have long tailed distributions of nodes that only approximate scale free ratios.

Department of Defense Initiatives

The U.S. military first became interested in network-centric warfare as an operational concept based on network science in 1996. John A. Parmentola, the U.S. Army Director for Research and Laboratory Management, proposed to the Army’s Board on Science and Technology (BAST) on December 1, 2003 that Network Science become a new Army research area. The BAST, the Division on Engineering and Physical Sciences for the National Research Council (NRC) of the National Academies, serves as a convening authority for the discussion of science and technology issues of importance to the Army and oversees independent Army-related studies conducted by the National Academies. The BAST conducted a study to find out whether identifying and funding a new field of investigation in basic research, Network Science, could help close the gap between what is needed to realize Network-Centric Operations and the current primitive state of fundamental knowledge of networks.

As a result, the BAST issued the NRC study in 2005 titled Network Science (referenced above) that defined a new field of basic research in Network Science for the Army. Based on the findings and recommendations of that study and the subsequent 2007 NRC report titled Strategy for an Army Center for Network Science, Technology, and Experimentation, Army basic research resources were redirected to initiate a new basic research program in Network Science. To build a new theoretical foundation for complex networks, some of the key Network Science research efforts now ongoing in Army laboratories address:

  • Mathematical models of network behavior to predict performance with network size, complexity, and environment
  • Optimized human performance required for network-enabled warfare
  • Networking within ecosystems and at the molecular level in cells.

As initiated in 2004 by Frederick I. Moxley with support he solicited from David S. Alberts, the Department of Defense helped to establish the first Network Science Center in conjunction with the U.S. Army at the United States Military Academy (USMA). Under the tutelage of Dr. Moxley and the faculty of the USMA, the first interdisciplinary undergraduate courses in Network Science were taught to cadets at West Point. In order to better instill the tenets of network science among its cadre of future leaders, the USMA has also instituted a five-course undergraduate minor in Network Science.

In 2006, the U.S. Army and the United Kingdom (UK) formed the Network and Information Science International Technology Alliance, a collaborative partnership among the Army Research Laboratory, UK Ministry of Defense and a consortium of industries and universities in the U.S. and UK. The goal of the alliance is to perform basic research in support of Network- Centric Operations across the needs of both nations.

In 2009, the U.S. Army formed the Network Science CTA, a collaborative research alliance among the Army Research Laboratory, CERDEC, and a consortium of about 30 industrial R&D labs and universities in the U.S. The goal of the alliance is to develop a deep understanding of the underlying commonalities among intertwined social/cognitive, information, and communications networks, and as a result improve our ability to analyze, predict, design, and influence complex systems interweaving many kinds of networks.

Subsequently, as a result of these efforts, the U.S. Department of Defense has sponsored numerous research projects that support Network Science.

Network properties

Often, networks have certain attributes that can be calculated to analyze the properties & characteristics of the network. These network properties often define network models and can be used to analyze how certain models contrast to each other. Many of the definitions for other terms used in network science can be found in Glossary of graph theory.

Density

The density D of a network is defined as a ratio of the number of edges E to the number of possible edges, given by the binomial coefficient \tbinom N2, giving D = \frac{2E}{N(N-1)}. Another possible equation is D = \frac{T}{N(N-1)}., whereas the ties T are unidirectional (Wasserman & Faust 1994).[2] This gives a better overview over the network density, because unidirectional relationships can be measured.

Size

The size of a network can refer to the number of nodes N or, less commonly, the number of edges E which can range from N-1 (a tree) to E_{max} (a complete graph).

Average degree

The degree k of a node is the number of edges connected to it. Closely related to the density of a network is the average degree, = \tfrac{2E}{N}. In the ER random graph model, we can compute = p(N-1) where p is the probability of two nodes being connected.

Average path length

Average path length is calculated by finding the shortest path between all pairs of nodes, adding them up, and then dividing by the total number of pairs. This shows us, on average, the number of steps it takes to get from one member of the network to another.

Diameter of a network

As another means of measuring network graphs, we can define the diameter of a network as the longest of all the calculated shortest paths in a network. It is the shortest distance between the two most distant nodes in the network. In other words, once the shortest path length from every node to all other nodes is calculated, the diameter is the longest of all the calculated path lengths. The diameter is representative of the linear size of a network.

Clustering coefficient

The clustering coefficient is a measure of an "all-my-friends-know-each-other" property. This is sometimes described as the friends of my friends are my friends. More precisely, the clustering coefficient of a node is the ratio of existing links connecting a node's neighbors to each other to the maximum possible number of such links. The clustering coefficient for the entire network is the average of the clustering coefficients of all the nodes. A high clustering coefficient for a network is another indication of a small world.

The clustering coefficient of the i'th node is

C_i = {2e_i\over k_i{(k_i - 1)}}\,,

where k_i is the number of neighbours of the i'th node, and e_i is the number of connections between these neighbours. The maximum possible number of connections between neighbors is, then,

{\binom {k}{2}} = + ... + {R_n \over n_{(outlinks)}}

Centrality measures

Information about the relative importance of nodes and edges in a graph can be obtained through centrality measures, widely used in disciplines like sociology. Centrality measures are essential when a network analysis has to answer questions such as: "Which nodes in the network should be targeted to ensure that a message or information spreads to all or most nodes in the network?" or conversely, "Which nodes should be targeted to curtail the spread of a disease?". Formally established measures of centrality are degree centrality, closeness centrality, betweenness centrality, eigenvector centrality, and katz centrality. The objective of network analysis generally determines the type of centrality measure(s) to be used.[14]

  • Degree centrality of a node in a network is the number of links (vertices) incident on the node.
  • Closeness centrality determines how "close" a node is to other nodes in a network by measuring the sum of the shortest distances (geodesic paths) between that node and all other nodes in the network.
  • Betweenness centrality determines the relative importance of a node by measuring the amount of traffic flowing through that node to other nodes in the network. This is done by measuring the fraction of paths connecting all pairs of nodes and containing the node of interest. Group Betweenness centrality measures the amount of traffic flowing through a group of nodes.[21]
  • Eigenvector centrality is a more sophisticated version of degree centrality where the centrality of a node not only depends on the number of links incident on the node but also the quality of those links. This quality factor is determined by the eigenvectors of the adjacency matrix of the network.
  • Katz centrality of a node is measured by summing the geodesic paths between that node and all (reachable) nodes in the network. These paths are weighted, paths connecting the node with its immediate neighbors carry higher weights than those which connect with nodes farther away from the immediate neighbors.

Spread of content in networks

Content in a complex network can spread via two major methods: conserved spread and non-conserved spread.[22] In conserved spread, the total amount of content that enters a complex network remains constant as it passes through. The model of conserved spread can best be represented by a pitcher containing a fixed amount of water being poured into a series of funnels connected by tubes . Here, the pitcher represents the original source and the water is the content being spread. The funnels and connecting tubing represent the nodes and the connections between nodes, respectively. As the water passes from one funnel into another, the water disappears instantly from the funnel that was previously exposed to the water. In non-conserved spread, the amount of content changes as it enters and passes through a complex network. The model of non-conserved spread can best be represented by a continuously running faucet running through a series of funnels connected by tubes . Here, the amount of water from the original source is infinite Also, any funnels that have been exposed to the water continue to experience the water even as it passes into successive funnels. The non-conserved model is the most suitable for explaining the transmission of most infectious diseases.

The SIR Model

In 1927, W. O. Kermack and A. G. McKendrick created a model in which they considered a fixed population with only three compartments, susceptible: S(t), infected, I(t), and recovered, R(t). The compartments used for this model consist of three classes:

  • S(t) is used to represent the number of individuals not yet infected with the disease at time t, or those susceptible to the disease
  • I(t) denotes the number of individuals who have been infected with the disease and are capable of spreading the disease to those in the susceptible category
  • R(t) is the compartment used for those individuals who have been infected and then recovered from the disease. Those in this category are not able to be infected again or to transmit the infection to others.

The flow of this model may be considered as follows:

{\color{blue}{\mathcal{S} \rightarrow \mathcal{I} \rightarrow \mathcal{R}}}

Using a fixed population, N = S(t) + I(t) + R(t), Kermack and McKendrick derived the following equations:

\frac{dS}{dt} = - \beta S I
\frac{dI}{dt} = \beta S I - \gamma I
\frac{dR}{dt} = \gamma I

Several assumptions were made in the formulation of these equations: First, an individual in the population must be considered as having an equal probability as every other individual of contracting the disease with a rate of \beta, which is considered the contact or infection rate of the disease. Therefore, an infected individual makes contact and is able to transmit the disease with \beta N others per unit time and the fraction of contacts by an infected with a susceptible is S/N. The number of new infections in unit time per infective then is \beta N (S/N), giving the rate of new infections (or those leaving the susceptible category) as \beta N (S/N)I = \beta SI (Brauer & Castillo-Chavez, 2001). For the second and third equations, consider the population leaving the susceptible class as equal to the number entering the infected class. However, a number equal to the fraction (\gamma which represents the mean recovery rate, or 1/\gamma the mean infective period) of infectives are leaving this class per unit time to enter the removed class. These processes which occur simultaneously are referred to as the Law of Mass Action, a widely accepted idea that the rate of contact between two groups in a population is proportional to the size of each of the groups concerned (Daley & Gani, 2005). Finally, it is assumed that the rate of infection and recovery is much faster than the time scale of births and deaths and therefore, these factors are ignored in this model.

More can be read on this model on the Epidemic model page.

Interdependent networks

An interdependent network is a system of coupled networks where nodes of one or more networks depend on nodes in other networks. Such dependencies are enhanced by the developments in modern technology. Dependencies may lead to cascading failures between the networks and a relatively small failure can lead to a catastrophic breakdown of the system. Blackouts are a fascinating demonstration of the important role played by the dependencies between networks. A recent study developed a framework to study the cascading failures in an interdependent networks system.[23][24]

Network optimization

Network problems that involve finding an optimal way of doing something are studied under the name of combinatorial optimization. Examples include network flow, shortest path problem, transport problem, transshipment problem, location problem, matching problem, assignment problem, packing problem, routing problem, Critical Path Analysis and PERT (Program Evaluation & Review Technique).

Network science research centers

Network analysis and visualization tools

  • Graph-tool and NetworkX, free and efficient Python modules for manipulation and statistical analysis of networks. [1] [2]
  • igraph, an open source C library for the analysis of large-scale complex networks, with interfaces to R, Python and Ruby.
  • pyunicorn, an open source Python package for the analysis of complex functional networks (for investigating statistical relations within sets of time series) and network-based nonlinear time series analysis. [3] [35]
  • Orange, a free data mining software suite, module orngNetwork
  • Pajek, program for (large) network analysis and visualization.
  • Tulip, a free data mining and visualization software dedicated to the analysis and visualization of relational data. [4]
  • SEMOSS, an RDF-based open source context-aware analytics tool written in Java leveraging the SPARQL query language.
  • ORA, a tool for Dynamic Network Analysis and network visualization.[36]

See also

Further reading

  • "Network Science Center," http://www.dodccrp.org/files/Network_Science_Center.asf
  • "Connected: The Power of Six Degrees," http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
  • "The Burgeoning Field of Network Science," http://themilitaryengineer.com/tme-articles/tme-past-articles/item/160-leader-profile-the-burgeoning-field-of-network-science
  • S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: From biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0-19-851590-1
  • Linked: The New Science of Networks, A.-L. Barabási (Perseus Publishing, Cambridge
  • Network Science, Committee on Network Science for Future Army Applications, National Research Council. 2005. The National Academies Press (2005)ISBN 0-309-10026-7
  • Network Science Bulletin, USMA (2007) ISBN 978-1-934808-00-9
  • The Structure and Dynamics of Networks Mark Newman, Albert-László Barabási, & Duncan J. Watts (The Princeton Press, 2006) ISBN 0-691-11357-2
  • Dynamical processes on complex networks, Alain Barrat, Marc Barthelemy, Alessandro Vespignani (Cambridge University Press, 2008) ISBN 978-0-521-87950-7
  • Network Science: Theory and Applications, Ted G. Lewis (Wiley, March 11, 2009) ISBN 0-470-33188-7
  • Nexus: Small Worlds and the Groundbreaking Theory of Networks, Mark Buchanan (W. W. Norton & Company, June 2003) ISBN 0-393-32442-7
  • Six Degrees: The Science of a Connected Age, Duncan J. Watts (W. W. Norton & Company, February 17, 2004) ISBN 0-393-32542-3
  • netwiki Scientific wiki dedicated to network theory
  • New Network Theory International Conference on 'New Network Theory'
  • Network Workbench: A Large-Scale Network Analysis, Modeling and Visualization Toolkit
  • Network analysis of computer networks
  • Network analysis of organizational networks
  • Network analysis of terrorist networks
  • Network analysis of a disease outbreak
  • Link Analysis: An Information Science Approach (book)
  • Connected: The Power of Six Degrees (documentary)
  • Influential Spreaders in Networks, M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, H.A. Makse, Nature Physics 6, 888 (2010)
  • A short course on complex networks
  • A course on complex network analysis by Albert-László Barabási

External links

  • Network Science Center at the U.S. Military Academy at West Point, NY
  • http://press.princeton.edu/titles/8114.html
  • http://www.cra.org/ccc/NSE.ppt.pdf
  • http://www.ifr.ac.uk/netsci08/
  • GNET — Group of Complex Systems & Random Networks
  • http://www.netsci09.net/
  • Cyberinfrastructure
  • Prof. Nicholas A Christakis' introduction to network science in Prospect magazine
  • Video Lectures on complex networks by Prof. Shlomo Havlin

Notes

  1. ^
  2. ^ http://psycnet.apa.org/journals/prs/9/4/172/
  3. ^ a b
  4. ^
  5. ^
  6. ^ a b c Braha, D. and Bar-Yam, Y. 2006. "From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks." Complexity 12: 59-63.
  7. ^ a b Hill, S.A. and Braha, D. 2010. "Dynamic Model of Time-Dependent Complex Networks." Physical Review E 82, 046105.
  8. ^ a b Gross, T. and Sayama, H. (Eds.). 2009. Adaptive Networks: Theory, Models and Applications. Springer.
  9. ^ a b Holme, P. and Saramäki, J. 2013. Temporal Networks. Springer.
  10. ^
  11. ^
  12. ^
  13. ^
  14. ^ a b Wasserman, Stanley and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.
  15. ^ Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010, ISBN 978-0199206650
  16. ^
  17. ^ Network analysis of terrorist networks
  18. ^ Barabási, A. L., Gulbahce, N., & Loscalzo, J. (2011). Network medicine: a network-based approach to human disease. Nature Reviews Genetics, 12(1), 56-68.
  19. ^
  20. ^
  21. ^ Puzis, R., Yagil, D., Elovici, Y., Braha, D. (2009) Collaborative attack on Internet users’ anonymity, Internet Research 19(1)
  22. ^ Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.
  23. ^
  24. ^
  25. ^ https://dnac.ssri.duke.edu/about.php
  26. ^ http://www-304.ibm.com/industries/publicsector/us/en/rep/!!/xmlid=229952
  27. ^ http://www.ns-cta.org/ns-cta-blog/
  28. ^ http://www.nest.rpi.edu/
  29. ^ http://lakshmi.calit2.uci.edu/cnra/
  30. ^ http://www.icensa.com/
  31. ^ http://www.hopkinsmedicine.org/institute_basic_biomedical_sciences/research_centers/high_throughput_biology_hit/technology_center_networks_pathways/
  32. ^ http://yins.yale.edu/
  33. ^ http://scnarc.rpi.edu/
  34. ^ http://warrencenter.upenn.edu/
  35. ^ J.F. Donges, J. Heitzig, B. Beronov, M. Wiedermann, J. Runge, Q.-Y. Feng, L. Tupikina, V. Stolbova, R.V. Donner, N. Marwan, H.A. Dijkstra, and J. Kurths, Unified functional network and nonlinear time series analysis for complex systems science: The pyunicorn package, preprint: arxiv.org:1507.01571
  36. ^ Kathleen M. Carley, 2014, ORA: A Toolkit for Dynamic Network Analysis and Visualization, In Reda Alhajj and Jon Rokne (Eds.) Encyclopedia of Social Network Analysis and Mining, Springer.
  37. ^ [5] Bejan A., Lorente S., The Constructal Law of Design and Evolution in Nature. Philosophical Transactions of the Royal Society B, Biological Science, Vol. 365, 2010, pp. 1335-1347.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.