Optimizing complex networks models

Analyzing real-world networks ultimately amounts at com- paring their empirical properties with the outcome of a proper, statistical model. The far most common, and most useful, ap- proach to define benchmarks rests upon the so-called canoni- cal formalism of statistical mechanics which has led to the defi- nition of the broad class of models known as Exponential Ran- dom Graphs (ERGs). Generally speaking, employing a model of this family boils down at maximizing a likelihood func- tion that embodies the available information about a certain system, hence constituting the desired benchmark. Although powerful, the aforementioned models cannot be solved ana- lytically, whence the need to rest upon numerical recipes for their optimization. Generally speaking, this is a hard task, since real-world networks can be enormous in size (for ex- ample, consisting of billions of nodes and links), hence re- quiring models with ‘many’ parameters (say, of the same or- der of magnitude of the number of nodes). This evidence calls for optimization algorithms which are both fast and scal- able: the collection of works constituting the present thesis represents an attempt to fill this gap. Chapter 1 provides a quick introduction to the topic. Chapter 2 deals specifically with ERGs: after reviewing the basic concepts constituting the pillars upon which such a framework is based, we will discuss several instances of it and three different numerical techniques for their optimization. Chapter 3, instead, focuses on the detection of mesoscale structures and, in particular, on the formalism based upon surprise: as the latter allows any partition of nodes to be assigned a p-value, detecting a spe- cific, mesoscale structural organization can be understood as xxi the problem of finding the corresponding, most significant partition - i.e. an optimization problem whose score function is, precisely, surprise. Finally, chapter 4 deals with the appli- cation of a couple of ERGs and of the surprise-based formal- ism to cryptocurrencies (specifically, Bitcoin).