Graph Theory and Network Science: The Basics

graph theory and network science are two related academic fields that have found application in numerous commercial industries. the terms ‘graph’ and ‘network’ are synonymous and one or the other is favored depending on the domain of application. a rosetta stone of terminology is provided below to help ground the academic terms to familiar, real-world structures.

graph theory is a branch of discrete mathematics concerned with proving theorems and developing algorithms for arbitrary graphs (e.g. random graphs , lattices , hierarchies ). for example, can a graph with four vertices, seven edges, and structured according to the landmasses and bridges of königsberg have its edges traversed once and only once? from such problems, the field of graph theory has developed numerous algorithms that can be applied to any graphical structure irrespective of the domain it represents (i.e. irrespective of what the graph models in the real-world). examples of such developments are provided below:

• planar graphs : can a graph be laid onto a 2d surface such that no edges cross. this problem has application, for example, in circuit board design where no two wires can overlap.
• shortest paths : what is the minimum number of hops required to get from vertex a to vertex b in a graph? moreover, what is the path that was taken? this problem has applications in routing , automated reasoning , and planning .
• energy flows : if a continuous “energy field” is diffused out from a particular vertex (or set of vertices), how much energy do the other vertices in the graph receive? this problem is found in recommendation engines , knowledge discovery, artificial cognition/intelligence , ranking, and natural language processing .

in the domain of network science, researchers don’t study networks in the abstract, but instead, they study numerous real-world representations in order to understand the universal properties of networks. examples of such networks include social networks , transportation networks , gene regulatory networks , knowledge networks , scholarly networks , etc. network science is a relatively new discipline that has only been able to blossom because of computer technologies. with computers, scientists are able analyze large-scale networks such as the world wide web which has approximately 500 billion nodes. due to their size, such structures tend to be studied from a statistical perspective.

• degree distribution : if a node is randomly selected from the network, what is the probability that it has x number of edges emanating from it? this statistic has implications for understanding how disease spreads through a social network and how communication networks can be sabotaged by directed attacks.
• assortative mixing : do nodes with characteristic a tend to connect to nodes with characteristic b? such information is useful as a descriptive statistic as well as for inferring future connectivity patterns in the network.
• growth models : do all real-world networks grow according to a similar rule? network growth models have implications for designing learning systems and understanding the future statistics of a fledgling network.

perhaps the crowning achievement of network science is the realization that most “real-world” networks have a similar structure. such networks are called scale-free networks and their degree distribution has an exponential decay. what this means is that real-world networks tend to have few nodes with numerous links and numerous nodes with few links. prior to recent times, most people assumed that networks were randomly connected. in the late 90s and early 00s a mass of scholarly articles were published demonstrating the prevalence of scale-free networks in nearly every possible domain imaginable.

interestingly, because most natural networks have this connectivity pattern, the processes that are evaluated on such networks are nearly the same—the only difference being the semantics as defined by the domain. for example, recommending products is analogous to determining the flow within an electrical circuit or determining how sensory data propagates through a neural network. finding friends in a social network is analogous to routing packets in a communication network or determining the shortest route on a transportation network. ranking web pages is analogous to determining the most influential people in a social network or finding the most relevant concepts in a knowledge network. finally, all these problems are variations of one general process— graph traversing . graph traversing is the simple process of moving from one vertex to another vertex over the edges in the graph and either mutating the structure or collecting bits of information along the way. the result of a traversal is either an evolution of the graph or a statistic about the graph.

the tools and techniques developed by graph theorists and networks scientists has an astounding number of practical applications. interestingly enough, once one has a general understanding of graph theory and network science, the world’s problems start to be seen as one in the same problem.

related material

rodriguez, m.a., neubauer, p., “ the graph traversal pattern ,” graph data management: techniques and applications, eds. s. sakr, e. pardede, igi global, isbn:9781613500538, august 2011.

watkins, j.h., m.a. rodriguez, “ a survey of web-based collective decision making systems ,” studies in computational intelligence: evolution of the web in artificial intelligence environments, springer-verlag, pages 245-279, 2008.

rodriguez, m.a., “ a graph-based movie recommender engine ,” marko a. rodriguez blog, 2011.

rodriguez, m.a., “ graphs, brains, and gremlin ,” marko a. rodriguez blog, 2011.