GRAPH THEORY AND ALGORITHMS:

OPTIMAL INFORMATION SPREADING

NEW APPROACHES TO "THE GOSSIP PROBLEM" AND SELF REPAIRING GRAPHS

Developed new approaches to modeling the spread of information over networks, i.e. Gossip algorithms, by studying temporal evolution of the information matrix in addition to adjacency matrix.

Edge formation in the optimal (2n-4) time evolving adjacency matrix was mapped to row addition on an NxN identity matrix, where row i represents node i's information. The properties of this new matrix were analyzed via spectral and statistical analyses and percolation methods. 

Two classes of gossip algorithms were developed, both satisfying 2n-4 steps from creation to "information stability," where all nodes have all information.  Random graphs and self-repairing graphs were both analyzed. 

MORE INFORMATION AVAILABLE UPON REQUEST.

Link to Github - https://github.com/dgoldsmith93/InformationSpreading

 

New York, NY, USA

  • 25231

©2017 by Daniel Goldsmith.