Concepts»Concepts 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 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. 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: cartogram: 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, 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. 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). contact matrix: critical point: 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. 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: the longest path in a graph. 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: A link between a pair of nodes denoting a predefined relation between them. 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. 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. graph (aka network): a collection of nodes and edges greedy algorithm: Horton-Strahler numbers (or just Strahler numbers): log-log plot: master equation mean-field theory: 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? 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: preferential attachment: random network: random walk: 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: 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. spherical cow: synchronization: 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. weighted graph: a graph with weighted edges.