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)

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

Advertisements

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.

http://ebeshero.github.io/thalaba/cytosc.html

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

 

New Developments in the Thalaba Antisocial Network Analysis

Practical Matters: Working in Cytoscape:

See my Tutorial, An Introduction to Network Analysis and Cytoscape for XML Coders for a much more detailed explanation of how to read and make network graphs, and step-by-step advice on things you can do and try with Cytoscape’s network analyzer tools.

Sample .tsv file for import to Cytoscape:

Use import wizard to designate nodes and edges, and node + edge attributes for use in labelling info.

Eliminate self-loops and remove duplicated edges in Edit menu (or find ways to filter out unnecessary information that clutters your graph).

Use the Network Analyzer to calculate network statistics. Think about them. Choose among graphical layouts with care.

Of interest in my original graph was Betweenness Centrality of Nodes. Where does my network of places break (cutpoints)? Metaplaces were essential to network coherence.

Now, I’ve generated some new graphs to simplify our view of the places, eliminate the clutter of line-group nodes (moving that information to the edges). And I’m interested in Path Lengths of Edges (Average Shortest Path Length), and Closeness of Nodes.

Here’s a new network graph oriented to Closeness Centrality of Nodes (SVG output from Cytoscape).

I’m also measuring the Eccentricity of the Nodes–how far they are from each other, which produced a rather remarkable result: (SVG output from Cytoscape)

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

BenFranklin

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: : https://plus.google.com/communities/106531799213972398416
 
 
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! 

 

Digital Mitford Annual June Workshop Set: June 2, 3, and 4.

Mitford Puzzle
Mary Russell Mitford in Pieces!

Calling all our Digital Mitford editors, and inviting new people to join us! We’re hosting our second annual Digital Mitford Projects Workshops at the beautiful Pitt-Greensburg campus again, in the first week of June. (Arrive Sunday June 1, depart Thurs. June 5). Details to come. We’re likely to have the cost of the residence on campus covered, but probably can’t cover travel funds on our own (waiting to hear from a grant application…) For now, we ask our editors and new editors to look about for local funding sources…and we’ll keep you posted! (Editors, look for a more detailed e-mail to follow soon.)

Project Overhaul: Pacific Update!

Exhausted, happy, a little anxious about not being prepared for the week ahead, I’ve spent the entire weekend overhauling and updating Digital Archives and Pacific Cultures, and I confess to great fascination and love for this project. I discover that we’re probably better known on our mirror site at obdurodon.org, which is right and proper, since our site was raised in an Australian monotreme’s nest and maintains a home there. I needed to update the site with the results of our course projects from the Digital Humanities course last December: new voyage files, graphs, charts, and maps—adventures with latitude and longitude extraction and conversion from 18th-century records. We’re making a point of sharing resources on the Pacific voyages that are hard to find, and this has sent us to studying the Forsters, father and son, who accompanied Captain Cook on his second circumnavigation voyage and shared an in-depth perspective on their cultural encounters with Pacific islanders.

So, this weekend Georg Forster (the younger Forster) sent me off on an unexpected adventure chasing after, I kid you not, belching seals in ancient Greek with diacritical markings. We autotagged the Forster texts from ancient word processing files sent us by Nicholas Thomas, who’d edited them for print publication–and we’re grateful to have them since they’re the ONLY digital resource we have of their work! But autotagging TEI XML from old word-processing files of gigantic voyage publications is fraught with perils, one of them being that you lose track of ancient Greek text that didn’t manage to be typed in a Unicode font. So, I happened to stumble into a passage of nonsense that, on consulting the printed text, turned out indeed to be the kind of classical Greek with an impressive variety of little accents and circumflexes and suchlike… and after some dedicated research of a few hours on Saturday, I was able to produce this:

We fell in with many herds of sea-bears, and sea-lions, which we did not attack, as another party was sent out upon that errand. We observed however, that these two species, though sometimes encamped on the same beach, always kept at a great distance asunder, and had no communication with each other. A strong rank stench is common to them, as well as to all other seals; a circumstance as well known to the ancients, as their inactivity and drowsiness whilst they lie on shore.

__________Φῶκαι νέποδες__________ 

ἀθρόαι εὕδουσιν, πολιῆς ἁλὸς ἐξαναδὐσαι, 

πικρὸν ἀποπνείουσαι ἁλὸς πολυβενθέος ὀδμήν.

 Webfooted seals forsake the whitening waves,
And sleep in herds, exhaling nauseous stench. 

Rowing along shore, we fell in with a spot where several thousand shags had built their nests, on those elevated tufts which I have mentioned before. Here was an opportunity to provide the whole ship’s company with a fresh meal, which was not neglected. The birds were for the greatest part so tame, as to let our boat’s crew come among them with clubs and staves; by which means several hundreds of them were killed. On this day’s excursion we found a bird of a new genus, which was of the size of a pigeon, and perfectly white. It belonged to the class of wading water-fowl, its toes were half webbed, and its eyes, as well as the base of the bill, surrounded by many little white glands or warts. It had such an horrid offensive smell, that we could not taste the flesh, though at this time we were not easily disgusted. 

It’s a wonderfully stinky passage–redolent of much of what ought to fascinate us about the Pacific voyages if we could only read them in fascinating snippets like this. Forster’s source for the Greek is none other than the Odyssey’s Book 4, as I quickly learned from the Perseus Project.

Meanwhile, the question is whether I’ve mismanaged my time horribly by posting students’ project work from last December rather than concentrating on the steadily aging digital grading piles my students have submitted this semester. I don’t know, but I can say this: I’m glad I had students to help with the Pacific project, and that they’ve had a chance to contribute to some real research resources—their time was not wasted and the Worldwide Web of Ideas is smarter because of their work and my finally getting around to posting it. And the site is actually fun, after all—if you haven’t spun one of our Google Earth KML viewers and read out bits of the voyages, it’s high time to go try that out… Spin Cook’s Second Voyage map over to the Cape of Good Hope and read about the fire-in-the-water from  the wee phosphorescent floating creatures that Cook and company sampled in buckets to study, and be amazed at the sight of strange worlds and the pungent odors of unknown species!

Project Update: Headnotes for the Digital Mitford

We’re hard at work on the Digital Mitford…an update:

Digital Mitford

We’ve not had a blog update from the Digital Mitford in a while, but our project team has been busy! We’ve been working on grant writing and conference talks, not to mention semester and job activities, our energies diverted in many directions. We need a Coding Refresher Hangout, so project-team members, please check your e-mail and write back to let me know what upcoming Saturdays might work for this.

I’m taking a moment now to think aloud about Headnotes for the literary editions we aim to prepare this year for the Digital Mitford. We’re working on coding a test-bed of files, a cross-section of Mitford’s letters, prose fiction, and drama composed in the early 1820s. This moment is especially significant for us in representing Mitford and, effectively, for gluing together the fragments of her reputation. (Victorianists know her for her prose fiction, Our Village, while Romanticists–if they’re aware of…

View original post 627 more words