ETD system

Electronic theses and dissertations repository

 

Tesi etd-05172014-163550


Thesis type
Tesi di dottorato di ricerca
Author
MAINARDI, SIMONE
URN
etd-05172014-163550
Title
Large-Scale Networks: Algorithms, Complexity and Real Applications
Settore scientifico disciplinare
ING-INF/05
Corso di studi
INGEGNERIA
Commissione
tutor Prof. Lenzini, Luciano
relatore Ing. Gregori, Enrico
tutor Prof. Mingozzi, Enzo
Parole chiave
  • cross correlations
  • complexity analysis
  • clustering
  • graph algorithms
Data inizio appello
18/06/2014;
Consultabilità
completa
Riassunto analitico
Networks have broad applicability to real-world systems, due to their ability to model and represent complex relationships. The discovery and forecasting of insightful patterns from networks are at the core of analytical intelligence in government, industry, and science. Discoveries and forecasts, especially from large-scale networks commonly available in the big-data era, strongly rely on fast and efficient network algorithms.<br><br>Algorithms for dealing with large-scale networks are the first topic of research we focus on in this thesis. We design, theoretically analyze and implement efficient algorithms and parallel algorithms, rigorously proving their worst-case time and space complexities. Our main contributions in this area are novel, parallel algorithms to detect k-clique communities, special network groups which are widely used to understand complex phenomena. The proposed algorithms have a space complexity which is the square root of that of the current state-of-the-art. Time complexity achieved is optimal, since it is inversely proportional to the number of processing units available. Extensive experiments were conducted to confirm the efficiency of the proposed algorithms, even in comparison to the state-of-the-art. We experimentally measured a linear speedup, substantiating the optimal performances attained.<br><br>The second focus of this thesis is the application of networks to discover insights from real-world systems. We introduce novel methodologies to capture cross correlations in evolving networks. We instantiate these methodologies to study the Internet, one of the most, if not the most, pervasive modern technological system. We investigate the dynamics of connectivity among Internet companies, those which interconnect to ensure global Internet access. We then combine connectivity dynamics with historical worldwide stock markets data, and produce graphical representations to visually identify high correlations. We find that geographically close Internet companies offering similar services are driven by common economic factors. We also provide evidence on the existence and nature of hidden factors governing the dynamics of Internet connectivity. Finally, we propose network models to effectively study the Internet Domain Name System (DNS) traffic, and leverage these models to obtain rankings of Internet domains as well as to identify malicious activities.<br>
File