Graph Theory — On To Network Theory

Among others, these are a few examples of classic network theory problems:Shortest Path Problem — What’s the shortest (cost-wise) path between any two nodes in a graph?Network Flow — Does the directed path have enough capacity to carry the “flow” it receives at each node along the way?Matching Problem — Does a graph contain a pair or more of matching independent edge sets?Critical Path Analysis — In a system of interdependent activities, which is the longest path of a dependent nature?At A Glance — Social Media NetworksBy investigating the similarities & differences of mainstream social medias through graph theory principles, we can deepen our understanding & appreciation of these everyday entities..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.Lightning NetworkThe 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..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.IOTA TangleThe 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..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).In ClosingStarting 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:Free and Open-Source Tool for Social Network AnalysisSocial Network Analysis: Social Network Visualizer (SocNetV) is a user-friendly and free software tool for Social…socnetv.orgGephi – The Open Graph Viz PlatformGephi is the leading visualization and exploration software for all kinds of graphs and networks.. More details

Leave a Reply