Concepts»Concepts

Concepts.Concepts History

Hide minor edits - Show changes to markup

Changed line 94 from:

Watts-Strogatz network: Most popular model for the small-world 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 small-world due to the small characteristic length that is obtained.

to:

Watts-Strogatz network: Most popular model for the small-world 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 small-world due to the small characteristic length that is obtained.

Changed line 94 from:

Watts-Strogatz network: Most popular model for the small-world 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 small-world due to the small characteristic length that is obtained.

to:

Watts-Strogatz network: Most popular model for the small-world 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 small-world due to the small characteristic length that is obtained.

January 05, 2011, at 08:17 PM by 76.19.173.183 -
Changed line 16 from:

There are many types of centrality, including degree, eccentricity, closeness, stress, betweenness centrality, eigenvector 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 real-valued 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, community centrality, 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 real-valued 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 88-89 from:

small-world property: short caracteristic length in a graph.

to:

small-world 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:

Watts-Strogatz network: First model for the small-world networks. It start with a regular network and by rewiring nodes with a fixed probability it becomes small-world due to the small caracteristic lenght obtained.

to:

Watts-Strogatz network: Most popular model for the small-world 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 small-world due to the small characteristic length that is obtained.

Changed lines 22-23 from:

configuration model: The ensemble of random graphs with a specified degree-distribution (contrast with Erdos-Renyi random graph). (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 degree-distribution (contrast with Erdos-Renyi random graph).

Changed lines 38-39 from:

edge: An edge is a pair of nodes.

to:

edge: A pair of nodes.

Changed line 42 from:

giant component: the biggest connected sub-graph.

to:

giant component: the largest connected sub-graph whose size scales proportionally to the size of (i.e., number of nodes in) the graph as the size goes to infinity.

January 07, 2010, at 04:48 PM by 201.211.255.144 -
Changed lines 34-35 from:

diameter:

to:

diameter: the longest path in a graph.

Changed lines 42-43 from:

giant component:

to:

giant component: the biggest connected sub-graph.

Changed lines 50-51 from:

log-log plot: How to turn Angelina Jolie into a straight line.

to:

log-log plot:

Changed lines 70-71 from:

power law: The key to ultimate wisdom. :)

to:

power law:

Changed lines 78-79 from:

recursion: CS mantra. See also: recursion.

to:

recursion:

Changed lines 88-89 from:

small-world property:

to:

small-world property: short caracteristic length in a graph.

Changed lines 94-96 from:

Watts-Strogatz network:

weighted graph:

to:

Watts-Strogatz network: First model for the small-world networks. It start with a regular network and by rewiring nodes with a fixed probability it becomes small-world due to the small caracteristic lenght obtained.

weighted graph: a graph with weighted edges.

August 11, 2009, at 07:50 PM by 76.19.173.183 -
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 Girvan-Newman 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 Girvan-Newman 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. 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.

March 02, 2009, at 08:53 PM by 132.239.145.147 -
Changed line 40 from:

Erdos-Renyi random graph:

to:

Erdos-Renyi 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 56-58 from:

modularity: this presentation does a good job defining network modularity and givine a lot of germane background.

to:

modularity: 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 7-12 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 Girvan-Newman 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 Girvan-Newman 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 15-16 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, 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, 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 real-valued function that depends only on the structure of the graph and no other outside information.

Changed lines 28-31 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 38-39 from:

edge:

to:

edge: An edge is a pair of nodes.

Changed line 42 from:

giant component

to:

giant component:

Deleted line 1:

fake blog ping, doorst5; holiday 100 search: search lookup | home loans

Added line 2:

fake blog ping, doorst5; holiday 100 search: search lookup | home loans

Added lines 1-93:

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 non-directed 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 Girvan-Newman 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, 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 betweenness-based methods (from Girvan-Newman), clustering methods (such as single linkage clustering and average linkage clustering), "local" methods (such as the Bagrow-Bollt l-shell 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 degree-distribution (contrast with Erdos-Renyi random graph). (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 community-detection 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 plot---for 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:

Erdos-Renyi random graph:

giant component

graph (aka network): a collection of nodes and edges

greedy algorithm:

Horton-Strahler numbers (or just Strahler numbers):

log-log plot: How to turn Angelina Jolie into a straight line.

master equation

mean-field theory:

modularity: 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.

Perron-Frobenius theorem:

phase transition

power law: The key to ultimate wisdom. :)

preferential attachment:

random network:

random walk:

recursion: CS mantra. See also: recursion.

renormalization:

scale-free network: (put good definition here) The Barabasi-Albert RMP review article from 2002 discusses scale-free networks in gory detail.

simulated annealing:

singular value decomposition:

small-world property:

spherical cow:

synchronization:

Watts-Strogatz network:

weighted graph: