Edit filter log

''''Network science''' is a new discipline that combines [[computer science]] together with network theory and [[graph theory]]. Network Science examines the interconnections among diverse physical or [[communication networks|engineered networks]], [[information networks]], [[Biological neural network|biological networks]], cognitive and [[semantic networks]], and [[social networks]]. This field of science seeks to discover common principles, algorithms and tools that govern network behavior. The 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." == 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). 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 off-shoot 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. Subsequently, the U.S. Department of Defense has funded numerous research projects in the area of 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. Today, network science is an exciting and growing interdisciplinary field. Scientists from many diverse fields are working together. Network science holds the promise of increasing collaboration across disciplines, by sharing data, algorithms, and software tools. == Network Properties == Often times, 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|Glossary of graph theory]]. === Density === The density <math>D</math> of a network is defined as a ratio of the number of edges <math>E</math> to the number of possible edges, given by the [[binomial coefficient]] <math>\tbinom N2</math>, giving <math>D = \frac{2E}{N(N-1)}.</math> === Size === The size of a network can refer to the number of nodes <math>N</math> or, less commonly, the number of edges <math>E</math> which can range from <math>N-1</math> (a tree) to <math>E_{max}</math> (a complete graph). === Average Degree === The degree <math>k</math> of a node is the number of edges connected to it. Closely related to the density of a network is the average degree, <math><k> = \tfrac{2E}{N}</math>. In the ER random graph model, we can compute <math><k> = pN(N-1)</math> where <math>p</math> 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. 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. <math>C_i = {2e_i\over k_i{(k_i - 1)}}</math> Maximum hypothetical connections between neighbors: <math>{\binom {K}{2}} = {{k(k-1)}\over 2}</math> === Connectedness === The way in which a network is connected plays a large part into how networks are analyzed and interpreted. Networks are classified in three different categories: * ''Clique''/''Complete Graph'': a completely connected network, where all nodes are connected to every other node. These networks are symmetric in that all nodes have in-links and out-links from all others. * ''Giant Component'': A single connected component which contains most of the nodes in the network. * ''Weakly Connected Component'': A collection of nodes in which there exists a path from any node to any other, ignoring directionality of the edges. * ''Strongly Connected Component'': A collection of nodes in which there exists a ''directed'' path from any node to any other. ===Node Centrality=== Node centrality can be viewed as a measure of influence or importance in a network model. There exists three main measures of Centrality that are studied in Network Science. *''Closeness'': represents the average distance that each node is from all other nodes in the network *''Betweeness'': represents the number of shortest paths in a network that traverse through that node *''Degree''/''Strength'': represents the amount links that a particular node possesses in a network. In a directed network, one must differentiate between in-links and out links by calculating in-degree and out-degree. The analogue to degree in a weighted network, strength is the sum of a node's edge weights. In-strength and out-strength are analogously defined for directed networks. == Network Models == Network models serve as a foundation to understanding interactions within empirical complex networks. Various [[random graph]] generation models produce network structures that may be used in comparison to real-world complex networks. === Erdős–Rényi Random Graph model === [[File:ER model.png|thumb|This [[Erdős–Rényi model]] is generated with N=4 nodes. For each edge in the complete graph formed by all N nodes, a random number is generated and compared to a given probability. If the random number is greater than p, an edge is formed on the model.]] The '''Erdős–Rényi model''', named for [[Paul Erdős]] and [[Alfréd Rényi]], is used for generating [[random graph]]s in which edges are set between nodes with equal probabilities. It can be used in the [[probabilistic method]] to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs. To generate an Erdős–Rényi model two parameters must be specified: the number of nodes in the graph generated as <math>N</math> and the probability that a link should be formed between any two nodes as <math>p</math>. A constant <math><k></math> may derived from these two components with the formula <math><k> = 2E/N = p(N-1)</math>. The Erdős–Rényi model has several interesting characteristics in comparison to other graphs. Because the model is generated without bias to particular nodes, the degree distribution is binomial in nature with regards to the formula: <math>P(\operatorname{deg}(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k}</math>. Also as a result of this characteristic, the clustering coefficient tends to 0. The model tends to form a giant component in situations where <tt><k> > 1</tt> in a process called [[percolation]]. The average path length is relatively short in this model and tends to <math>log(N)</math>. === Watts-Strogatz Small World model === [[File:Watts-Strogatz-rewire.png|thumb|The [[Watts and Strogatz model]] uses the concept of rewiring to achieve its structure. The model generator will iterate through each edge in the original lattice structure. An edge may changed its connected vertices according to a given rewiring probability. <math><k> = 4</math> in this example.]] The [[Watts and Strogatz model]] is a random graph generation model that produces graphs with [[small-world properties]]. An initial lattice structure is used to generate a Watts-Strogatz model. Each node in the network is initially linked to its <math><k></math> closest neighbors. Another parameter is specified as the rewiring probability. Each edge has a probability <math>p</math> that it will be rewired to the graph as a random edge. The expected number of rewired links in the model is <math>pE = pN<k>/2</math>. As the Watts-Strogatz model begins as non-random lattice structure, it has a very high clustering coefficient along with high average path length. Each rewire is likely to create a shortcut between highly connected clusters. As the rewiring probability increases, the clustering coefficient decreases slower than the the average path length. In effect, this allows the average path length of the network to decrease significantly with only slightly decreases in clustering coefficient. Higher values of p force more rewired edges, which in effect makes the Watts-Strogatz model a random network. === Barabási–Albert (BA) Preferential Attatchment model === The [[Barabási–Albert model]] is a random network model used to demonstrate a preferential attachment or a "rich-get-richer" effect. In this model, an edge is most likely to attach to nodes with higher degrees. The network begins with an initial network of ''m''₀ nodes. ''m''₀&nbsp;≥&nbsp;2 and the degree of each node in the initial network should be at least&nbsp;1, otherwise it will always remain disconnected from the rest of the network. In the BA model, new nodes are added to the network one at a time. Each new node is connected to <math>m</math> existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability ''p''_''i'' that the new node is connected to node ''i'' is<ref name=RMP>{{Cite journal | url =http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/StatisticalMechanics_Rev%20of%20Modern%20Physics%2074,%2047%20(2002).pdf | author1 = R. Albert | author2 = A.-L. Barabási | title = Statistical mechanics of complex networks | journal = [[Reviews of Modern Physics]] | volume = 74 | pages = 47–97 | year = 2002 | doi = 10.1103/RevModPhys.74.47 | author = Albert, Réka | bibcode=2002RvMP...74...47A }}</ref> : <math>p_i = \frac{k_i}{\sum_j k_j},</math> where ''k''_''i'' is the degree of node ''i''. Heavily linked nodes ("hubs") tend to quickly accumulate even more links, while nodes with only a few links are unlikely to be chosen as the destination for a new link. The new nodes have a "preference" to attach themselves to the already heavily linked nodes. [[Image:Barabasi-albert model degree distribution.svg|thumb|The degree distribution of the BA Model, which follows a power law. In loglog scale the power law function is a straight line.<ref name=Barabasi1999 />]] The degree distribution resulting from the BA model is scale free, in particular, it is a power law of the form: : <math>P\left(k\right)\sim k^{-3} \, </math> Hubs exhibit high betweenness centrality which allows short paths to exist between nodes. As a result the BA model tends to have very short average path lengths. The clustering coefficient of this model also tends to 0. ===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: <math>S(t)</math>, infected, <math>I(t)</math>, and recovered, <math>R(t)</math>. The compartments used for this model consist of three classes: * <math>S(t)</math> is used to represent the number of individuals not yet infected with the disease at time t, or those susceptible to the disease * <math>I(t)</math> 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 * <math>R(t)</math> 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: : <math>\color{blue}\mathcal{S} \rightarrow \mathcal{I} \rightarrow \mathcal{R}</math> Using a fixed population, <math>N = S(t) + I(t) + R(t)</math>, Kermack and McKendrick derived the following equations:<br /> : <math>\frac{dS}{dt} = - \beta S I </math> : <math>\frac{dI}{dt} = \beta S I - \gamma I </math> : <math>\frac{dR}{dt} = \gamma I </math> 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 <math>\beta</math>, 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 <math>\beta N</math> others per unit time and the fraction of contacts by an infected with a susceptible is <math>S/N</math>. The number of new infections in unit time per infective then is <math>\beta N (S/N)</math>, giving the rate of new infections (or those leaving the susceptible category) as <math>\beta N (S/N)I = \beta SI</math> (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 (<math>\gamma</math> which represents the mean recovery rate, or <math>1/\gamma</math> 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. ==Network analysis== ===Social network analysis=== '''[[Social network]] analysis''' examines the structure of relationships between social entities.<ref>Wasserman, Stanley and Katherine Faust. 1994. ''Social Network Analysis: Methods and Applications.'' Cambridge: Cambridge University Press. </ref> These entities are often persons, but may also be [[Group (sociology)|groups]], [[organizations]], [[nation states]], [[web sites]], [[scientometrics|scholarly publications]]. Since the 1970s, the empirical study of networks has played a central role in social science, and many of the [[Mathematics|mathematical]] and [[Statistics|statistical]] tools used for studying networks have been first developed in [[sociology]].<ref name="Newman">Newman, M.E.J. ''Networks: An Introduction.'' Oxford University Press. 2010</ref> Amongst many other applications, social network analysis has been used to understand the [[diffusion of innovations]], news and rumors. Similarly, it has been used to examine the spread of both [[epidemiology|diseases]] and [[Medical sociology|health-related behaviors]]. It has also been applied to the [[Economic sociology|study of markets]], where it has been used to examine the role of trust in [[Social exchange|exchange relationships]] and of social mechanisms in setting prices. Similarly, it has been used to study recruitment into [[political movement]]s and social organizations. It has also been used to conceptualize scientific disagreements as well as academic prestige. More recently, network analysis (and its close cousin [[traffic analysis]]) has gained a significant use in military intelligence, for uncovering insurgent networks of both hierarchical and [[leaderless resistance|leaderless]] nature. ===Biological network analysis=== With the recent explosion of publicly available high throughput biological data, the analysis of molecular networks has gained significant interest. The type of analysis in this content are closely related to social network analysis, but often focusing on local patterns in the network. For example [[network motif]]s are small subgraphs that are over-represented in the network. [[Activity motifs]] are similar over-represented patterns in the attributes of nodes and edges in the network that are over represented given the network structure. ===Link analysis=== Link analysis is a subset of network analysis, exploring associations between objects. An example may be examining the addresses of suspects and victims, the telephone numbers they have dialed and financial transactions that they have partaken in during a given timeframe, and the familial relationships between these subjects as a part of police investigation. Link analysis here provides the crucial relationships and associations between very many objects of different types that are not apparent from isolated pieces of information. Computer-assisted or fully automatic computer-based link analysis is increasingly employed by [[bank]]s and [[insurance]] agencies in [[fraud]] detection, by telecommunication operators in telecommunication network analysis, by medical sector in [[epidemiology]] and [[pharmacology]], in law enforcement [[Criminal procedure|investigation]]s, by [[search engine]]s for [[relevance]] rating (and conversely by the [[search engine spammer|spammers]] for [[spamdexing]] and by business owners for [[search engine optimization]]), and everywhere else where relationships between many objects have to be analyzed. ====Network robustness==== The structural robustness of networks <ref>{{cite book |title= Complex Networks: Structure, Robustness and Function | author =R. Cohen, S. Havlin|year= 2010 |publisher= Cambridge University Press |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php}}</ref> is studied using [[percolation theory]]. When a critical fraction of nodes is removed the network becomes fragmented into small clusters. This phenomenon is called percolation <ref>{{cite book |title= Fractals and Disordered Systems | author =A. Bunde, S. Havlin|year= 1996 |publisher= Springer |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_fds.php}}</ref> and it represents an order-disorder type of [[phase transition]] with [[critical exponents]]. ====Pandemic Analysis==== The [[SIR Model]] is one of the most well known algorithms on predicting the spread of global pandemics within an infectious population. =====Susceptible to Infected===== <math>S = \beta(1/N)</math> The formula above describes the "force" of infection fore each susceptible unit in an infectious population, where {{math|&beta;}} is equivalent to the transmission rate of said disease. To track the change of those susceptible in an infectious population: <math>\Delta S = \beta \times S {1\over N} \Delta t</math> =====Infected to Recovered===== <math>\Delta I = \mu I\Delta t</math> Over time, the number of those infected fluctuates by: the specified rate of recovery, represented by <math>\mu</math> but deducted to one over the average infectious period <math>{1\over \tau}</math>, the numbered of infecious individuals, <math>I</math>, and the change in time, <math>\Delta t</math>. =====Infectious Period===== Whether a population will be overcome by a pandemic, with regards to the SIR model, is dependent on the value of <math>R_0</math> or the "average people infected by an infected individual." <math>R_0 = \beta\tau = {\beta\over\mu}</math> ====Web Link Analysis==== Several [[Web search]] [[ranking]] algorithms use link-based centrality metrics, including (in order of appearance) [[Massimo Marchiori|Marchiori]]'s [[Hyper Search]], [[Google]]'s [[PageRank]], Kleinberg's [[HITS algorithm]], the [[CheiRank]] and [[TrustRank]] algorithms. Link analysis is also conducted in information science and communication science in order to understand and extract information from the structure of collections of web pages. For example the analysis might be of the interlinking between politicians' web sites or blogs. =====PageRank===== PageRank works by randomly picking "nodes" or websites and then with a certain probability, "randomly jumping" to other nodes. By randomly jumping to these other nodes, it helps PageRank completely traverse the network as some webpages exist on the periphery and would not as readily be assessed. Each node, <math>x_i</math>, has a PageRank as defined by the sum of pages <math>j</math> that link to <math>i</math> times one over the outlinks or "out-degree" of <math>j</math> times the "importance" or PageRank of <math>j</math>. <math>x_i = \sum_{j\rightarrow i}{1\over N_j}x_j^{(k)}</math> ======Random Jumping====== As explained above, PageRank enlists random jumps in attempts to assign PageRank to every website on the internet. These random jumps find websites that might not be found during the normal search methodologies such as [[Breadth-First Search]] and [[Depth-First Search]]. In an improvement over the aforementioned formula for determining PageRank includes adding these random jump components. Without the random jumps, some pages would receive a PageRank of 0 which would not be good. The first is <math>\alpha</math>, or the probability that a random jump will occur. Contrasting is the "damping factor", or <math>1 - \alpha</math>. <math>R{(p)} = {\alpha\over N} + (1 - \alpha) \sum_{j\rightarrow i}{1\over N_j}x_j^{(k)}</math> Another way of looking at it: <math>R(A) = \sum {R_B\over B_{(outlinks)}} + ... + {R_n \over n_{(outlinks)}}</math> ===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]]. For example, [[eigenvector centrality]] uses the [[eigenvectors]] of the [[adjacency matrix]] to determine nodes that tend to be frequently visited. ==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. Subsequently, the U.S. Department of Defense has funded numerous research projects in the area of 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. ==Spread of content in networks== Content in a [[complex network]] can spread via two major methods: conserved spread and non-conserved spread.<ref>Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.</ref> 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]]. ==Interdependent networks== Interdependent networks 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.<ref>{{Cite journal|author = S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin |title = Catastrophic cascade of failures in interdependent networks|journal = Nature |volume = 464 |pages = 1025–28 |year = 2010 | doi=10.1038/nature08932 |issue=7291|url=http://havlin.biu.ac.il/Publications.php?keyword=Catastrophic+cascade+of+failures+in+interdependent+networks&year=*&match=all}}</ref> <ref>{{cite journal|last=Jianxi Gao|first=Sergey V. Buldyrev3, Shlomo Havlin4, and H. Eugene Stanley|title=Robustness of a Network of Networks|journal=Phys. Rev. Lett|year=2011|volume=107|pages=195701|url=http://havlin.biu.ac.il/Publications.php?keyword=Robustness+of+a+Tree-like+Network+of+Interdependent+Networks&year=*&match=all | doi = 10.1103/PhysRevLett.107.195701 }}</ref> ==Network optimization== Network problems that involve finding an optimal way of doing something are studied under the name of [[combinatorial optimization]]. Examples include [[flow network|network flow]], [[shortest path problem]], [[transport problem]], [[transshipment problem]], [[location problem]], [[Matching (graph theory)|matching problem]], [[assignment problem]], [[packing problem]], [[routing| routing problem]], [[Critical Path Analysis]] and [[PERT]] (Program Evaluation & Review Technique). ==Network Analysis and Visualization Tools== *[[Graph-tool]] and [[NetworkX]], [[Free Software|free]] and efficient Python modules for manipulation and statistical analysis of networks. [http://graph-tool.skewed.de/] [http://networkx.lanl.gov/] *[[Orange (software)|Orange]], a free data mining software suite, module [http://www.ailab.si/orange/doc/modules/orngNetwork.htm orngNetwork] *[http://pajek.imfm.si/doku.php Pajek], program for (large) network analysis and visualization. *[[Tulip (software)|Tulip]], a free data mining and visualization software dedicated to the analysis and visualization of relational data. [http://tulip.labri.fr/] ==See also== * [[Complex network]] * [[Collaborative innovation network]] * [[Dynamic network analysis]] * [[Glossary_of_graph_theory|Glossary of Graph Theory]] * [[Higher category theory]] * [[Immune network theory]] * [[Irregular warfare]] * [[Network Theory in Risk Assessment]] * [[Polytely]] * [[Systems theory]] *[[Constructal law]]<ref>[http://www.constructal.org/en/art/Phil.%20Trans.%20R.%20Soc.%20B%20%282010%29%20365,%201335%961347.pdf] 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.</ref> *[[Percolation]] *[[Network Theory in Risk Assessment]] *[[Network topology]] *[[Network analyzer]] *[[Small-world networks]] *[[Social-circles network model|Social circles]] *[[Scale-free networks]] *[[Sequential dynamical system]] ==References== * "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 * R. Cohen, K. Erez, D. ben-Avraham, S. Havlin, "[http://havlin.biu.ac.il/Publications.php?keyword=Resilience+of+the+Internet+to+random+breakdown&year=*&match=all Resilience of the Internet to random breakdown]" Phys. Rev. Lett. 85, 4626 (2000). * R. Cohen, K. Erez, D. ben-Avraham, S. Havlin, "[http://havlin.biu.ac.il/Publications.php?keyword=Breakdown+of+the+Internet+under+intentional+attack&year=*&match=all Breakdown of the Internet under intentional attack]" Phys. Rev. Lett. 86, 3682 (2001) * R. Cohen, S. Havlin, "[http://havlin.biu.ac.il/Publications.php?keyword=Scale-free+networks+are+ultrasmall&year=*&match=all Scale-free networks are ultrasmall]" Phys. Rev. Lett. 90, 058701 (2003) == Further reading== * "The Burgeoning Field of Network Science," http://themilitaryengineer.com/index.php?option=com_content&task=view&id=88 * 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 * ''[http://www.nap.edu/catalog.php?record_id=11516 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 0470331887 * ''Nexus: Small Worlds and the Groundbreaking Theory of Networks'', Mark Buchanan (W. W. Norton & Company, June 2003) ISBN 0393324427 * ''Six Degrees: The Science of a Connected Age'', Duncan J. Watts (W. W. Norton & Company, February 17, 2004) ISBN 0393325423 *[http://netwiki.amath.unc.edu/ netwiki] Scientific wiki dedicated to network theory *[http://www.networkcultures.org/networktheory/ New Network Theory] International Conference on 'New Network Theory' *[http://nwb.slis.indiana.edu/ Network Workbench]: A Large-Scale Network Analysis, Modeling and Visualization Toolkit *[http://www.orgnet.com/SocialLifeOfRouters.pdf Network analysis of computer networks] *[http://www.orgnet.com/orgnetmap.pdf Network analysis of organizational networks] *[http://firstmonday.org/htbin/cgiwrap/bin/ojs/index.php/fm/article/view/941/863 Network analysis of terrorist networks] *[http://www.orgnet.com/AJPH2007.pdf Network analysis of a disease outbreak] *[http://linkanalysis.wlv.ac.uk/ Link Analysis: An Information Science Approach] (book) *[http://gephi.org/2008/how-kevin-bacon-cured-cancer/ Connected: The Power of Six Degrees] (documentary) *[http://havlin.biu.ac.il/Publications.php?keyword=Identification+of+influential+spreaders+in+complex+networks++&year=*&match=all 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) *[http://havlin.biu.ac.il/course4.php A short course on complex networks] == External links== * [http://www.netscience.usma.edu 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/ * [http://www.fis.ua.pt/grupoteorico/gteorico.htm GNET] &mdash; Group of Complex Systems & Random Networks * http://www.netsci09.net/ * [http://cns.slis.indiana.edu/cyber.html Cyberinfrastructure] * [http://www.prospectmagazine.co.uk/2010/02/let%E2%80%99s-all-be-friends/ Prof. Nicholas A Christakis' introduction to network science in Prospect magazine] *[http://havlin.biu.ac.il/videos1.php Video Lectures on complex networks] by [[Shlomo Havlin|Prof. Shlomo Havlin]] ==Notes== {{reflist}} [[Category:Cybernetics]] [[Category:Networks]] [[Category:Network theory]] [[fr:Science des réseaux]] [[nl:Netwerkwetenschap]] [[de:Netzwerkforschung]] [[es:Análisis de redes]] [[fr:Théorie des réseaux]] [[ko:네트워크 이론]] [[pt:Análise de rede]] [[fi:Verkkoteoria]]'