Graph Theory and Network Science

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

Read the full article on DZONE.  

Keywords:  Graph Theory • Network Science