|//No Comment - The Blockchain, Technology Beats Algorithms & Bridges in Complex Networks|
|Written by Alex Armstrong|
|Tuesday, 20 December 2016|
• The Blockchain: A Gentle Four Page Introduction
• Technology Beats Algorithms (in Exact String Matching)
• Bridges in Complex Networks
Sometimes the news is reported well enough elsewhere and we have little to add other than to bring it to your attention.
No Comment is a format where we present original source information, lightly edited, so that you can decide if you want to follow it up.
Just about everyone is convinced that the blockchain, as introduced and used by Bitcoin, is a key technology of the future. So knowing how it works might be a good investment:
Blockchain is a distributed database that keeps a chronologicallygrowing list (chain) of records (blocks) secure from tampering and revision. While computerisation has changed the nature of a ledger from clay tables in the old days to digital records in modern days, blockchain technology is the first true innovation in record keeping that could potentially revolutionise the basic principles of information keeping. In this note, we provide a brief self contained introduction to how the blockchain works.
And the good news is that this is another story of Alice and Bob.
Also see: Inside Bitcoin - The Block Chain
We all love thinking about non-obvious algorithms that do things so much faster than the obvious approach. This is almost what computer science at its best is all about but what if we were misguided and the way to do things faster isn't to invent better algorithms but improve the hardware. It seems that this is indeed the case in the all important area of string matching:
More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the naive algorithm exploiting SIMD instructions of modern CPUs (with symbols compared in a special order) is the fastest one for patterns of length up to about 50 symbols and extremely good for longer patterns and small alphabets.
The algorithm compares 16 or 32 characters in parallel by applying SSE2 or AVX2 instructions, respectively. Moreover, it uses loop peeling to further speed up the searching phase. We tried several orders for comparisons of pattern symbols and the increasing order of their probabilities in the text was the best.
Graphs are both fun to study and sometimes important. Graphs in theory come in all sorts but what about the ones we find in the real world are just random. An edge i.e. a connection in a graph that, if removed breaks the graph into two disconnected parts, i.e. there isn't an alternative connection, is obviously important - its called a bridge.
The question is to real networks have random bridges?:
A bridge in a graph is an edge whose removal disconnects the graph and increases the number of connected components. We calculate the fraction of bridges in a wide range of real-world networks and their randomized counterparts.
We find that real networks typically have more bridges than their completely randomized counterparts, but very similar fraction of bridges as their degree-preserving randomizations.
We define a new edge centrality measure, called bridgeness, to quantify the importance of a bridge in damaging a network. We find that certain real networks have very large average and variance of bridgeness compared to their degree-preserving randomizations and other real networks.
Finally, we offer an analytical framework to calculate the bridge fraction , the average and variance of bridgeness for uncorrelated random networks with arbitrary degree distributions.
or email your comment to: email@example.com
|Last Updated ( Wednesday, 21 December 2016 )|