Using Measures of Network Complexity to Observe and Shape Networks
A unique feature of networks is their ability to be expressed through myriad forms. For instance, network-like structures are commonly used in computer science. Object-oriented languages make extensive use of trees (a structure somewhat similar to networks) for many features like searches and data organization while functional languages like OCaml are unique in their own recursive definitions to establish trees in a manner that is quite distinct from OO-languages yet identical in functionality [1]. Looking away from computer science, however, networks are scrutinized greatly by mathematicians, who look at the structure in a manner far uniquely different from computer scientists. Part of their analysis involves the parameterization of networks, since networks that grow increasingly complex can be difficult to characterize without the aid of quantitative measures. One excerpt from a larger work called “Quantitative Measures of Network Complexity” aggregrates many such methods into an organized textbook-like presentation [2]. The vertex degree magnitude is a particular measurement of interest that assigns coefficients representative of network complexity magnitude, incorporating network parameters like branches, cycles and cliques. Such a measurement can certainly be employed in large networks, yet the issue arises of considering other network features and their impact on such a measurement. For instance, the vertex degree magnitude appears to not be normalized for parameters like size, which makes comparisons of networks based purely on edge distribution/density more challenging. Another metric, the average edge complexity, can be normalized by the number of edges to better indicate the average node degree between networks of different size. Plenty of other metrics exist, yet many of them incorporate similar parameters like the degree of loops, branches and centrality to highlight different aspects of network complexity.
These parameters are typically unaffected by network sizes in that, although their magnitude increases with larger networks, they can be normalized by the number of nodes or edges. This provides a strong basis for any type of complexity metric, and these parameters can be employed to standardize networks of massive proportions, particularly those from the web. As the number of sites linked in the strongly connected component of the web grows (for context, this number has risen from 56 million in 2000 to 1.8 billion in 2014), drawing comparisons over time becomes possible only with the usage of such parameters, which can provide unique insight into the means of development and potential differences between types of structures [3, 4]. The bow-tie structure, from which both of these numbers originate, could be further inspected with metrics of complexity to indicate more about the strongly-connected component or the frequency and location of tendrils off the ‘bow’ portions of the web. And even moving beyond web networks, such properties can be used for subjective terms–someone looking for a specific type of network may define ‘ideal’ parameters and, using measurements like vertex degree magnitude or average edge complexity, maximize their ‘ideal’ measurement with quantitative backing. The latter type of work delves into shaping a network to a user’s preferences, which is important for companies that use networks to extract or encode information. For the former, web search engines like Google’s could find great value in obtaining more information about the world wide web network as it seeks results based on user queries. Using PageRank first to help organize the network by putting weights on nodes, Google could adopt a subset of the web network it believes is relevant to a search and verify that truth through parameterization. Even more interesting would be the automation of network generation through classification of parameters, a technique that may see use for those looking to generate networks with a particular set of edges, that can be perfected through adjustments to its formation based on the values of parameters to indicate its ‘idealness’. The mathematical basis of networks can be potent not just for network identification but for its manipulation and restructuring, and the usage of networks as a means to convey information can be automated through the use of algorithms that adjust magnitudes of network complexity.
— Nikhil Saggi
Referenced works:
[1] http://www.cs.cornell.edu/courses/cs3110/2018fa/textbook/data/trees.html
[2] https://link.springer.com/content/pdf/10.1007/0-387-25871-X_5.pdf
[3] https://dl.acm.org/citation.cfm?id=346290
[4] http://planet-data.org/sites/default/files/publications/GraphStructureRevisited.pdf