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 graphslatticeshierarchies). 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:
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 networkstransportation networksgene regulatory networks,knowledge networksscholarly 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.