Social Network Analysis for Startups

Chapter 2. Graph Theory—A Quick Introduction

What Is a Graph?

A graph is, arguably, one of the most ubiquitous mathematical abstractions. Even if you have never encountered this mathematical concept before, you have most likely worked with graphs before. A project plan is a graph; a circuit diagram is a graph; dependencies between files in a software project are graph.

In this book, we shall mostly deal with one type of graph—social graphs or social networks. A social network is simply a collection of sentences that describe relationships, in the following way:

Alice ----likes-----> Bob
(noun)    (verb)     (noun)

The simple phrase above is a basic unit of social network analysis called a dyad. Every dyad denotes a single relationship—an edge in traditional graph theory (although I use the words edge and relationship interchangeably). The nouns in the phrase represent people involved in the relationship—these are called vertices (plural of vertex) or nodes in the mathematical literature (we shall use nodes exclusively).

In social network analysis, nodes have a type. Each node could represent a person, organization, a blog posting, a hashtag, etc. If a graph contains nodes of only one type, it’s called a 1-mode graph. If it contains relationships between two types, it’s bimodal or 2-mode. We can also have multimodal graphs.

We shall start our exploration of social networks with 1-mode graphs—i.e., graphs that link people to people, organizations to organizations, words to words, and so on. We ...