Some Key Locational Terms and Concepts in Network Analysis

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)


Borgatti, Stephen P. “Centrality and Network Flow.” Social Networks 27 (2005) 55–71.

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).

A Network Analysis and Cytoscape Tutorial

I’ve finally completed a tutorial I’d long promised on network analysis and plotting graphs with Cytoscape, making use of the Network Analyzer tools to exemplify important concepts in graph theory! It’s probably riddled with errors, so thanks for any feedback and corrections here. It is also liberally dotted with screen captures, and I hope this provides a useful, in-depth introduction.

This accompanies my posts here on Locational Terms and Concepts in Network Analysis  and on my Thalaba Network Analysis Project.


Day of DH 2014, and Pennsylvania Digital Humanists–Forming a Network?


There is a new Keystone DH Group forming on the Day of DH 2014 site, initially organized by Chris Long at Penn State University and Diane Jackaci at Bucknell University. It’s an effort to organize DH people from the state of PA together, and it could be good for interested Pennsylvanians to help build this and promote it. (Who knows–we could find ourselves pooling resources to organize a “PADH” conference or some such madness!) 
The group is organizing through Day of DH 2014, coming up next Tues. April 8. I’ve just signed up to participate in Day of DH and to join the Keystone DH group there (on the group pages). If you’re here with me in the state of PA, and you work on digital humanities projects you may want to sign up, too! 
Keystone DH Google Plus Community Page: :
The Keystone Group seems to be just now forming–not many members yet: I know there are many more of us DH-istas here in PA, and it would be great to see us all form a supportive network! 


Our Digital Humanities Course This Fall

Much excitement as we work on the Pacific Project for our Digital Humanities course this fall! Here’s a link to our course site in progress:

We’ll be putting together the course schedule in August, when we’re also moving to a new Greensburg campus server.