November 27, 2018
Beyond Calculus
Finally, our path in this series of graph theory articles takes us to the heart of a burgeoning sub-branch of graph theory: network theory.
Network theory is the application of graph-theoretic principles to the study of complex, dynamic interacting systems
It provides techniques for further analyzing the structure of interacting agents when additional, relevant information is provided. The applications of network theory, as stated in the articles leading up to this piece (3), are far-reaching & industry-agnotisc. From computer science, to electrical engineering, to game-theory & social media analysis, the fundamentals of network theory offer a powerful mental model to increase our understanding of modern systems.
Without spoiling too much of future articles, it might make sense to provide a quick overview of the type of problems that network theory is commonly used to solve. Among others, these are a few examples of classic network theory problems:
By investigating the similarities & differences of mainstream social medias through graph theory principles, we can deepen our understanding & appreciation of these everyday entities. Let’s break down the structure of Medium & Facebook through mini graph-like representations.
What does a graph representing Medium (this very site) look like? Start by zoning-in on the relationship between users. On Medium, a user can follow another user without that second user necessarily following the first user back — this means that each edge on the Medium graph has direction. Medium’s network, therefore, takes the form of a directed graph. For example, as seen below, me & a friend, Tony Stark, can both follow Julie Zhuo (an insanely talented product designer at Facebook & prolific Medium writer I follow IRL); however, since she has no interest in seeing what we write, she doesn’t follow us back —there is no path back from Julie to Tony & myself. This is expressed visually in the example below:
Let’s now compare the above Medium representation with the Big-Blue controversial guilty-pleasure, Facebook. Excluding the relatively recent “follow” feature, Facebook users have to be friends in order to share access to each others content. One Facebook user requests a second Facebook user to become friends. Once this request is accepted, however, it no longer matters who sent the request to whom. Directionality no longer exists: both users will see each other’s content on their respective timelines. Let’s continue our example of an influencer Julie, with two normal users myself & Tony Stark. On Facebook, it’s highly likely that Tony & I are friends; however, neither of us are friends with Julie:
We’ve gone through two thought experiments with mainstream social medias as an exercise to visually understand their respective graph-like structure. Let’s head over to the exciting world of cryptocurrencies in order to glance through two more examples.
We’ll now analyze another graph-like modern-marvel: cryptocurrencies. Below, instead of thinking through examples, we’ll analyze literal screenshots of supporting networks for both Bitcoin’s Lightning Network & IOTA’s Tangle consensus mechanism.
The graph above is a screenshot of the Lightning Network, a p2p, off-chain settlement layer for Bitcoin — one of the most hopeful scaling solutions for instant, near-free Bitcoin transactions. The Lightning Network is a network composed of nodes & payment channels (aka edges). Payment channels are strictly made of two end-nodes, which, by sending an initial amount to open the payment channel, is what allows for extremely fast Bitcoin transactions between both connecting nodes. In order to join the Lightning Network, a node needs to have a minimum of a at least one payment channel open with another node.
Nodes & payment channels, as introduced above, combine for a classic example of a graph-like structure. Once a payment channel is open, both users can send transactions back & forth endless —direction goes both ways, which means that the Lightning Network represents an undirected graph.
The IOTA project, on the other hand, launched a peculiar consensus mechanism for their version of a blockchain, based on a DAG — Directed Acyclic Graph.
In the Tangle, displayed above, each transaction is represented as a vertex in the graph. When a new transaction joins the Tangle, it chooses two previously unconfirmed transactions to confirm, adding two new edges & nodes to the graph. Once confirmed, the confirmed transactions can no longer be confirmed by incoming unconfirmed transactions; but recently joined unconfirmed transaction can & likely will be confirmed by the next incoming, unconfirmed transaction. Thus, depending on whether a transactions has been confirmed or unconfirmed, leads to directionality within the graph. Observing above, we can verify this by noticing that most singular vertices near the bottom side of the graph have two edges & vertices hanging off them (unconfirmed transactions waiting to be confirmed).
Starting from the very basics of graph theory history with the Seven Bridges of Konigsberg, we’ve now progressed all the way through to the center of network theory. Yet this is only launchpad for actual graph & network theory applications — the next step is to play around with the many well-made graph & network visualization & analysis tools such as the ones linked below:
sources
