Concepts.Concepts History
Hide minor edits  Show changes to output
Changed line 94 from:
'''WattsStrogatz network''': Most popular model for the smallworld networks (and the first model that came out of the applied math and physics [[http://customizeddogcollars.com/customizeddogcollars.html  community]]). It start with a regular network and by rewiring nodes with a fixed probability it becomes smallworld due to the small characteristic length that is obtained.
to:
'''WattsStrogatz network''': Most popular model for the smallworld networks (and the first model that came out of the applied math and physics community. It start with a regular network and by rewiring nodes with a fixed probability it becomes smallworld due to the small characteristic length that is obtained.
Changed line 94 from:
'''WattsStrogatz network''': Most popular model for the smallworld networks (and the first model that came out of the applied math and physics community). It start with a regular network and by rewiring nodes with a fixed probability it becomes smallworld due to the small characteristic length that is obtained.
to:
'''WattsStrogatz network''': Most popular model for the smallworld networks (and the first model that came out of the applied math and physics [[http://customizeddogcollars.com/customizeddogcollars.html  community]]). It start with a regular network and by rewiring nodes with a fixed probability it becomes smallworld due to the small characteristic length that is obtained.
Changed line 16 from:
There are many types of centrality, including '''degree''', '''eccentricity''', '''closeness''', '''stress''', '''betweenness centrality''', '''eigenvector centrality''', [[http://wwwpersonal.umich.edu/~mejn/centrality/  community centrality]], and '''connectedness''' (see Fowler's work on the legislation cosponsorship networks). One could also count the '''clustering coefficient''' introduced by Watts and Strogatz to it. Since these measures are very varied, it is not easy to find a strict definition but the least to require is that a centrality measure is a realvalued function that depends only on the structure of the graph and no other outside information.
to:
There are many types of centrality, including '''degree''', '''eccentricity''', '''closeness''', '''stress''', '''betweenness centrality''', '''eigenvector centrality''', [[http://wwwpersonal.umich.edu/~mejn/centrality/  community centrality]], [[http://www.necsi.edu/research/networks/com122/com122.pdf  Dynamic Centrality]] and '''connectedness''' (see Fowler's work on the legislation cosponsorship networks). One could also count the '''clustering coefficient''' introduced by Watts and Strogatz to it. Since these measures are very varied, it is not easy to find a strict definition but the least to require is that a centrality measure is a realvalued function that depends only on the structure of the graph and no other outside information.
Changed line 38 from:
'''edge''': A pair of nodes.
to:
'''edge''': A link between a pair of nodes denoting a predefined relation between them.
Changed lines 8889 from:
'''smallworld property''': short caracteristic length in a graph.
to:
'''smallworld property''': when the diameter of a graph scales as the logarithm of the number of nodes (or even a smaller scaling) as the number of nodes goes to infinity.
Changed line 94 from:
'''WattsStrogatz network''': First model for the smallworld networks. It start with a regular network and by rewiring nodes with a fixed probability it becomes smallworld due to the small caracteristic lenght obtained.
to:
'''WattsStrogatz network''': Most popular model for the smallworld networks (and the first model that came out of the applied math and physics community). It start with a regular network and by rewiring nodes with a fixed probability it becomes smallworld due to the small characteristic length that is obtained.
Changed lines 2223 from:
'''configuration model''': The ensemble of random graphs with a specified degreedistribution (contrast with ErdosRenyi random graph). ([[Profiles/Mason]]: I don't really understand the terminology, but it is the standard one.)
to:
'''configuration model''': The ensemble of random graphs with a specified degreedistribution (contrast with ErdosRenyi random graph).
Changed lines 3839 from:
'''edge''': An edge is a pair of nodes.
to:
'''edge''': A pair of nodes.
Changed line 42 from:
'''giant component''': the biggest connected subgraph.
to:
'''giant component''': the largest connected subgraph whose size scales proportionally to the size of (i.e., number of nodes in) the graph as the size goes to infinity.
Changed lines 3435 from:
to:
'''diameter''': the longest path in a graph.
Changed lines 4243 from:
to:
'''giant component''': the biggest connected subgraph.
Changed lines 5051 from:
'''loglog plot''': How to turn Angelina Jolie into a straight line.
to:
Changed lines 7071 from:
'''power law''': The key to ultimate wisdom. :)
to:
Changed lines 7879 from:
'''recursion''': CS mantra. See also: '''recursion'''.
to:
Changed lines 8889 from:
'''smallworld property''':
to:
'''smallworld property''': short caracteristic length in a graph.
Changed lines 9496 from:
'''WattsStrogatz network''':
'''weighted graph''':
to:
'''WattsStrogatz network''': First model for the smallworld networks. It start with a regular network and by rewiring nodes with a fixed probability it becomes smallworld due to the small caracteristic lenght obtained.
'''weighted graph''': a graph with weighted edges.
Changed line 7 from:
'''betweenness''': (put good definition here before the discussion of various types of betweenness) The betweenness is a quantitative measure that describes how much a node or edge is 'between' other nodes, i.e., how much this node is needed to forward information or other goods in various scenarios of transport over the network. The study of betweenness has a long history in social network analysis. One can consider betweenness with respect to different graph subcomponents; in particular, '''edge betweenness''' and '''node betweenness''' are commonly computed. In a common model, transport is considered to occur only on shortest paths and this is indeed the most common definition and may also be called '''geodesic betweenness'''. In another scenario, transport is envisioned to happen basically at random, resulting in '''random walk betweenness'''. The '''GirvanNewman community detectection algorithm''' iteratively calculates the betweenness centrality values of a graph, removes the subcomponent of interest with highest betweenness (of whatever type), until one obtains a dendrogram describing the graph's community structure.
to:
'''betweenness''': (put good definition here before the discussion of various types of betweenness) The betweenness is a quantitative measure that describes how much a node or edge is 'between' other nodes, i.e., how much this node is needed to forward information or other goods in various scenarios of transport over the network. The study of betweenness has a long history in social network analysis. One can consider betweenness with respect to different graph subcomponents; in particular, '''edge betweenness''' and '''node betweenness''' are commonly computed. In a common model, transport is considered to occur only on shortest paths and this is indeed the most common definition and may also be called '''geodesic betweenness'''. In another scenario, transport is envisioned to happen basically at random, resulting in '''random walk betweenness'''. The '''GirvanNewman community detectection algorithm''' iteratively calculates the betweenness centrality values of a graph, removes the subcomponent of interest with highest betweenness (of whatever type), until one obtains a dendrogram describing the graph's community structure. [[http://necsi.org/affiliates/braha/Internet_Research_Anonimity.pdf Group Betweenness Centrality (GBC)]] of a group of nodes stands for the fraction of shortest paths between pairs of nodes in a network that passes through at least one of the nodes in the group.
Changed line 40 from:
'''ErdosRenyi random graph''':
to:
'''ErdosRenyi random graph''': A random graph where for every pair of nodes, there is an edge between them, independent of any other pair, with probability p.
Changed lines 5658 from:
'''modularity''': [[ http://riotact.mit.edu/writings/6977_networks_modularity.pdf  this presentation]] does a good job defining network modularity and givine a lot of germane background.
to:
'''modularity''': [[ http://riotact.mit.edu/writings/6977_networks_modularity.pdf  this presentation]] does a good job defining network modularity and givine a lot of germane background. (For a given network partition, modularity is computed by adding all the edge weight for nodes in the same group and subtracting all the edge weight for nodes between groups, and then [when relevant] comparing it to the value the relative weights from some null model.)
'''network centralization''': Can be applied to any centrality measure. The idea is to take some network centrality measure and looking at a sort of variance in the network. What is the centrality distribution? How heterogeneous are things?
Changed lines 712 from:
'''betweenness''': (put good definition here before the discussion of various types of betweenness). The study of betweenness has a long history in social network analysis. One can consider betweenness with respect to different graph subcomponents; in particular, '''edge betweenness''' and '''node betweenness''' are commonly computed. One can also examine either '''geodesic betweenness''' (considering only the strictly shortest paths) and '''random walk betweenness'''. The '''GirvanNewman community detectection algorithm''' iteratively calculates the betweenness of a graph, removes the subcomponent of interest with highest betweenness (of whatever type), until one obtains a dendrogram describing the graph's community structure.
'''bipartite graph''':
'''bipartiteness''':
to:
'''betweenness''': (put good definition here before the discussion of various types of betweenness) The betweenness is a quantitative measure that describes how much a node or edge is 'between' other nodes, i.e., how much this node is needed to forward information or other goods in various scenarios of transport over the network. The study of betweenness has a long history in social network analysis. One can consider betweenness with respect to different graph subcomponents; in particular, '''edge betweenness''' and '''node betweenness''' are commonly computed. In a common model, transport is considered to occur only on shortest paths and this is indeed the most common definition and may also be called '''geodesic betweenness'''. In another scenario, transport is envisioned to happen basically at random, resulting in '''random walk betweenness'''. The '''GirvanNewman community detectection algorithm''' iteratively calculates the betweenness centrality values of a graph, removes the subcomponent of interest with highest betweenness (of whatever type), until one obtains a dendrogram describing the graph's community structure.
'''bipartite graph''': A bipartite graph is a graph whose node set can be partitioned into two sets such that no nodes in the same set share an edge.
'''bipartiteness''':
Changed lines 1516 from:
'''centrality''': (insert a good definition). The study of centrality has a long history in social network analysis. There are many types of centrality, including '''betweenness centrality''', '''eigenvector centrality''', [[http://wwwpersonal.umich.edu/~mejn/centrality/  community centrality]], '''connectedness''' (see Fowler's work on the legislation cosponsorship networks), and many others whose names I'm forgetting.
to:
'''centrality''': (insert a good definition). The study of centrality has a long history in social network analysis. It was introduced to quantify the structural impact an edge or node has on the processes over the network it is in. There are many types of centrality, including '''degree''', '''eccentricity''', '''closeness''', '''stress''', '''betweenness centrality''', '''eigenvector centrality''', [[http://wwwpersonal.umich.edu/~mejn/centrality/  community centrality]], and '''connectedness''' (see Fowler's work on the legislation cosponsorship networks). One could also count the '''clustering coefficient''' introduced by Watts and Strogatz to it. Since these measures are very varied, it is not easy to find a strict definition but the least to require is that a centrality measure is a realvalued function that depends only on the structure of the graph and no other outside information.
Changed lines 2831 from:
'''degree''':
'''degree distribution''':
to:
'''degree''': The degree of a node is defined as the number of edges it has.
'''degree distribution''': The degree distribution gives the number of nodes with a given degree k.
Changed lines 3839 from:
to:
'''edge''': An edge is a pair of nodes.
Changed line 42 from:
to:
Deleted line 1:
%white% [[http://fakeblogping5.infofake blog ping]], [[http://doorst5.infodoorst5]]; [[http://holiday100search.infoholiday 100 search]]: [[http://searcheslookup.infosearch lookup]]  [[http://searcheslookup.info/search.php?q=home+loanshome loans]]
Added line 2:
%white% [[http://fakeblogping5.infofake blog ping]], [[http://doorst5.infodoorst5]]; [[http://holiday100search.infoholiday 100 search]]: [[http://searcheslookup.infosearch lookup]]  [[http://searcheslookup.info/search.php?q=home+loanshome loans]]
Added lines 193:
This page has some concepts that are useful in network theory.
'''adjacency matrix''': In a network of n nodes, the adjacency matrix is an n by n matrix with binary entries indicating whether there is an edge between two nodes. 1 indicates an edge and 0 indicates no edge. For nondirected networks, the adjacency matrix is symmetric, i.e. entry i, j is equal to j, i. Naturally this symmetry does not hold for directed networks, where an edge between two nodes in one direction does not imply an edge between the nodes in the opposite direction.
'''assortativity''' (and disassortativity):
'''betweenness''': (put good definition here before the discussion of various types of betweenness). The study of betweenness has a long history in social network analysis. One can consider betweenness with respect to different graph subcomponents; in particular, '''edge betweenness''' and '''node betweenness''' are commonly computed. One can also examine either '''geodesic betweenness''' (considering only the strictly shortest paths) and '''random walk betweenness'''. The '''GirvanNewman community detectection algorithm''' iteratively calculates the betweenness of a graph, removes the subcomponent of interest with highest betweenness (of whatever type), until one obtains a dendrogram describing the graph's community structure.
'''bipartite graph''':
'''bipartiteness''':
'''cartogram''':
'''centrality''': (insert a good definition). The study of centrality has a long history in social network analysis. There are many types of centrality, including '''betweenness centrality''', '''eigenvector centrality''', [[http://wwwpersonal.umich.edu/~mejn/centrality/  community centrality]], '''connectedness''' (see Fowler's work on the legislation cosponsorship networks), and many others whose names I'm forgetting.
'''community structure''': (put good definition here before discussion of various types). There are many types of community detection algorithms, including betweennessbased methods (from GirvanNewman), clustering methods (such as single linkage clustering and average linkage clustering), "local" methods (such as the '''BagrowBollt lshell method''' and its generalizations), and modularity maximization. (The description in this paragraph needs serious improvement.)
'''complex (adpative) system''':
'''configuration model''': The ensemble of random graphs with a specified degreedistribution (contrast with ErdosRenyi random graph). ([[Profiles/Mason]]: I don't really understand the terminology, but it is the standard one.)
'''contact matrix''':
'''critical point''':
'''degree''':
'''degree distribution''':
'''dendrogram''': A tree used to represent a perfectly hierarchical community structure in a network. The output of almost every communitydetection algorithm is a dendrogram. (The prefix 'dendro' means that one uses length information in drawing lines and not just topology. In the networks literature, this is used as a drawing tool. In other contexts, this gives additional meaning to the plotfor example, in phylogenetic networks, it can indicate how many million years ago a branching in an evolutionary path occurred.)
'''diameter''':
'''directed graph''': A graph with signed edges. For example, in a protein interaction network, we have excitatory interactions (which might be represented by an edge with value +1) and inhibitory interactions (with edges of value 1).
'''edge''':
'''ErdosRenyi random graph''':
'''giant component'''
'''graph''' (aka network): a collection of nodes and edges
'''greedy algorithm''':
'''HortonStrahler numbers''' (or just Strahler numbers):
'''loglog plot''': How to turn Angelina Jolie into a straight line.
'''master equation'''
'''meanfield theory''':
'''modularity''': [[ http://riotact.mit.edu/writings/6977_networks_modularity.pdf  this presentation]] does a good job defining network modularity and givine a lot of germane background.
'''node''': A vertex in a graph. It might represent a Congressman, an actor, a piece of legislation, a protein, or any of myriad other things.
'''PageRank''': Think google...
'''percolation''': (put def here) There is both '''bond percolation''' and '''site percolation'''.
'''PerronFrobenius theorem''':
'''phase transition'''
'''power law''': The key to ultimate wisdom. :)
'''preferential attachment''':
'''random network''':
'''random walk''':
'''recursion''': CS mantra. See also: '''recursion'''.
'''renormalization''':
'''scalefree network''': (put good definition here) The BarabasiAlbert RMP review article from 2002 discusses scalefree networks in gory detail.
'''simulated annealing''':
'''singular value decomposition''':
'''smallworld property''':
'''spherical cow''':
'''synchronization''':
'''WattsStrogatz network''':
'''weighted graph''':


