Psychology Wiki
Don't have an account?
Register
Register
in: Networks, Network analysis, Network theory, Graph theory

Changes: Network analysis

Back to page
Sign in to edit
No edit summary
 
No edit summary
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{SocPsy}}
  
{{SocPsy}}
   
  +
'''Network theory''' is an area of [[computer science]] and [[network science]] and part of [[graph theory]]. It has application in many disciplines including statistical physics, [[particle physics]], computer science, [[biology]], [[economics]], [[operations research]], and [[sociology]]. Network theory concerns itself with the study of [[graph (mathematics)|graphs]] as a representation of either [[symmetric relation]]s or, more generally, of [[directed graph|asymmetric relations]] between discrete objects. Applications of network theory include [[Logistics|logistical]] networks, the [[World Wide Web]], Internet, [[gene regulatory network]]s, metabolic networks, [[social networks]], [[epistemological]] networks, etc. See [[list of network theory topics]] for more examples.
−
'''Network analysis''' is the analysis of networks through [[network theory]] (or more generally [[graph theory]]).
  
   
  +
==Network optimization==
−
The networks may be real as in a [[social network|social network]], or virtual, such as the [[Internet]].
  
   
−
Analysis include descriptions of ''structure'', such as [[small-world networks]], [[social-circles network model|social circles]] or [[scale-free networks]], ''optimisation'', such as [[Critical Path Analysis]] and [[PERT]] (Program Evaluation & Review Technique), and properties such as flow assignment.
 +
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==
−
'''Social network analysis''' maps relationships between individuals in [[social network]]s.
  
  ⚫
===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]].
  +
  +
====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.
   
 
===Centrality measures===
  
===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.
 +
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.
   
  +
==Spread of content in networks==
⚫
===Web link analysis===
  
   
  +
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]].
−
Several [[Web search]] [[rank]]ing algorithms use eigenvector-based centrality metrics, including [[Google]]'s [[PageRank]], Kleinberg's [[HITS algorithm]], and the [[TrustRank]] algorithm.
  
  +
  +
==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 = 465 |pages = 1025–28 |year = 2010 | doi=10.1038/nature08932 |issue=7291}}</ref>
  +
  +
==Implementations==
  +
*[[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==
  
==See also==
  +
*[[Bayesian network]]
  +
*[[Complex network]]
 
*[[Data mining]]
  
*[[Data mining]]
  +
*[[Dynamic network analysis]]
  +
*[[Percolation]]
  +
*[[Network science]]
  +
*[[Network topology]]
  +
*[[Network analyzer]]
  +
*[[Organizational network analysis]]
  ⚫
*[[Small-world networks]]
  +
*[[Social-circles network model|Social circles]]
  +
*[[Scale-free networks]]
  +
*[[Sequential dynamical system]]s
  +
  +
==Notes==
  +
{{reflist}}
  +
  +
==External links==
  +
*[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]
   
 
[[Category:Networks]]
  
[[Category:Networks]]
  ⚫
[[Category:Network analysis]]
  ⚫
[[Category:Network theory| ]]
 
[[Category:Graph theory]]
  
[[Category:Graph theory]]
⚫
[[Category:Research methods]]
  
⚫
[[Category:Social networks]]
  
⚫
[[Category:Sociology]]
  
−  
   
  +
<!--
⚫
:pt:Análise de redes
  
  +
[[de:Netzwerkforschung]]
⚫
{{enWP|Network analysis}}
  
  +
[[es:Análisis de redes]]
  +
[[fr:Théorie des réseaux]]
  +
[[ko:네트워크 이론]]
  ⚫
[[pt:Análise de rede]]
  +
[[fi:Verkkoteoria]]
  +
-->
  +
{{enWP|Network theory}}

Latest revision as of 01:11, 1 January 2012

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language | Individual differences | Personality | Philosophy | Social |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |

Social psychology: Altruism · Attribution · Attitudes · Conformity · Discrimination · Groups · Interpersonal relations · Obedience · Prejudice · Norms · Perception · Index · Outline

Network theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology. Network theory concerns itself with the study of graphs as a representation of either symmetric relations or, more generally, of asymmetric relations between discrete objects. Applications of network theory include logistical networks, the World Wide Web, Internet, gene regulatory networks, metabolic networks, social networks, epistemological networks, etc. See list of network theory topics for more examples.

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 analysis

Social network analysis

Social network analysis examines the structure of relationships between social entities.[1] These entities are often persons, but may also be groups, organizations, nation states, web sites, scholarly publications.

Since the 1970s, the empirical study of networks has played a central role in social science, and many of the mathematical and statistical tools used for studying networks have been first developed in sociology.[2] 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 diseases and health-related behaviors. It has also been applied to the study of markets, where it has been used to examine the role of trust in exchange relationships and of social mechanisms in setting prices. Similarly, it has been used to study recruitment into political movements 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 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 motifs 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 banks and insurance agencies in fraud detection, by telecommunication operators in telecommunication network analysis, by medical sector in epidemiology and pharmacology, in law enforcement investigations, by search engines for relevance rating (and conversely by the 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 [3] 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 [4] and it represents an order-disorder type of phase transition with critical exponents.

Web link analysis

Several Web search ranking algorithms use link-based centrality metrics, including (in order of appearance) 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.

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.

Spread of content in networks

Content in a complex network can spread via two major methods: conserved spread and non-conserved spread.[5] 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.[6]

Implementations

  • Graph-tool and NetworkX, free and efficient Python modules for manipulation and statistical analysis of networks. [1] [2]
  • 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. [3]

See also

Notes

  1. ↑ Wasserman, Stanley and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.
  2. ↑ Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010
  3. ↑ R. Cohen, S. Havlin (2010). Complex Networks: Structure, Robustness and Function, Cambridge University Press.
  4. ↑ A. Bunde, S. Havlin (1996). Fractals and Disordered Systems, Springer.
  5. ↑ Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.
  6. ↑ S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin (2010). Catastrophic cascade of failures in interdependent networks. Nature 465 (7291): 1025–28.

External links

This page uses Creative Commons Licensed content from Wikipedia (view authors).
Community content is available under CC-BY-SA unless otherwise noted.