Posts Tagged graph

Graph distance using matrix multiplication in Octave

Apr 1, 2014 at 09:54 · Filed under Mathish, Technology ·Tagged , , , , , ,

If A is a matrix of positive edge weights between nodes in a graph (from 0 to infinity), then power-iteration through multiplication of that matrix in the {R,min,plus} semi-ring will converge on the distances of the shortest-paths in that graph. For reference (my own mostly), this blog entry gives the GNU Octave code for it and an example.

Read the rest of this entry »

Leave a Comment

Barabási – Albert preferential attachment and the Internet

Dec 2, 2013 at 02:03 · Filed under Technology ·Tagged , , , , , , , , , , , ,

The Barabási – Albert paper “Emergence of Scaling in Random Networks” helped popularise the preferential-attachment model of graphs, and its relevance to a number of real-world graphs. There’s a small, somewhat trivial tweak to that model that can be made which never the less changes its characteristics slightly, with the result possibly being more relevant to the BGP AS graph. GNU Octave and Java implementations are given for the original BA-model and the tweak. The tweak can also potentially improve performance of vectorised implementations, such as Octave/Matlab.

Read the rest of this entry »

Comments (1)

Distributed k-Core Algorithm talk at CoNEXT 2012

Dec 12, 2012 at 10:13 · Filed under Technology ·Tagged , , , , , , , , ,

Our short paper / extended abstract was accepted for the ACM CoNEXT 2012 student workshop  in Nice, France. See also the slides for my very brief “pitch” talk (the even-numbered slides with text were my notes, and were not shown to the audience obviously). Somehow the talk was voted as 1 of the 8 best talks of the student workshop, and I got to give it again to the full conference the next day!

Comments (1)