Here is my own working list of key terms and definitions in network analysis. Several of these are also discussed in the wonderfully fun Six Degrees of Spaghetti Monsters blog site, with examples from the social network of Harry Potter. This list accompanies my tutorial on Network Analysis and Cytoscape for XML Coders and my Thalaba project post, “Spectacular Intersections of Place.”
Walk—A sequence of nodes and lines—with a beginning and end point node, Can double back on itself—may not be straight. A walk (as well as a trail and a path) has a length, number of lines.
Trail—A walk with distinct lines—no connection (or communication or link) is used more than once, but a node can come up more than once (doubling back).
Path—All nodes and all lines are distinct—No node is connected more than once along a path. This is a direct route.
Closed Walk—begins and ends at same node (loop).
Cycle—closed walk of 3+ nodes—all lines distinct—all nodes in between the start and finish are distinct (and the start node = finish node).
Tour—closed walk using each line in the whole graph.
Connected vs. Disconnected: Is there a path between all nodes in the graph? If disconnected, we can refer to components of the graph (connected units of it).
Geodesic: shortest path between two nodes. Geodesic distance: length of the shortest path. If there’s no path between nodes, the geodesic distance is either considered infinite or undefined, since they can’t be reached.
Eccentricity (or association number): largest geodesic distance between a node and any other node
Diameter of a graph: defined by the largest geodesic distance between two nodes.
Connectivity: Does a graph remain connected without particular nodes or lines?
Vulnerability: if a graph is easily broken at a few nodes or edges
Cutpoint and Cutset—Cutpoint= node that if removed makes multiple components (splits a unified graph) Cutset = set of nodes that maintains connectedness.
Bridge: Line (edge) critical to connectedness
Centralities of Various Kinds: A Useful Site for Telling Them Apart
Degree Centrality – The most central node has the highest number of ties to other nodes
Ego Density—a node’s ties / max number of possible ties
Closeness and Closeness Centrality: How quickly can a node interact with all the other nodes? Does the node need to rely on lots of other nodes to connect across the graph, or can it get to all these nodes relatively quickly?
Betweenness and Betweenness Centrality: Which nodes are in-between other nodes—which are necessary to control or mediate interactions?
Eigenvector Centrality: measures the influence of a node on the other nodes around it–a way of studying the relative importance of nodes to making other nodes more central
Random Walk Centrality: involves starting from any node and randomly moving about—how long it takes to traverse the network—sort of like pouring turning on a tap at one node and watching to see where the water runs.
Information and Information Centrality: Information of a path = inverse of its length. “In brief, the length of any path is directly related to the variance of transmitting a signal from one node to another; thus the information contained in this path is the reciprocal of this variance. Thus any path (and hence, each and every combined path) has an ‘information content.’” (Wasserman and Faust 194)
Clique: 3+ nodes adjacent to each other—a subset of nodes, in which no others are also adjacent to ALL the members. (Thalaba is full of cliques)
Small World: Most nodes aren’t connected to each other, but can be reached in one or two steps (strangers linked by mutual acquaintance)
Sources:
Borgatti, Stephen P. “Centrality and Network Flow.” Social Networks 27 (2005) 55–71. http://www.analytictech.com/borgatti/papers/centflow.pdf
Newman, M. E. J. “A measure of betweenness centrality based on random walks. arXiv:cond-mat/0309045v1 [cond-mat.stat-mech] (Submitted on 1 Sep 2003).
Wasserman, Stanley and Katherine Faust. Social Network Analysis: Methods and Applications (Cambridge UP, 1994).
Like this:
Like Loading...
Confessions of a Digital Romanticist 
