The Inverse Problem of Evolving Networks—with Application to Social Nets
Files
Description
Many complex systems can be modeled by graphs. The vertices of the graph represent objects of the system, and the edges of the graph the relationships between these objects. These relationships may be structural or functional, according to the modeler’s needs. Following scientific convention, in this paper we assume that all important information about a given system is encoded in this simple model; more precisely, in an attributed graph, where the vertices and edges may possess labels from a given alphabet. Let us give a few examples. In a citation network of scientific papers, the vertices model the papers, the edges the citations between them; the vertices can be labeled by the date of the paper, its authors, and probably a list of keywords. By including these and only these properties in the model, we implicitly neglect everything else, such as the title of the paper and the nationality and gender of the authors. In a network of airline flights, the vertices “are” airports and the edges represent direct flights between them. The vertices might be labeled with each airport’s number of terminals and home country, and the edges with the airlines and possibly the flight time. In a neural network model of synchronization in the hippocampus, one usually has to distinguish between pyramidal cells and interneurons; here the edges are the synapses from the presynaptic cells to the postsynaptic ones. Furthermore, the synapses can be excitatory or inhibitory. In this paper we study network evolution. For us, this term means that the structure of the networks, in other words the modeled complex systems, change in time. In the citation network, new papers are published and make new citations to other papers. In the airline network, new airports might be built or old ones might be shut down, new flights introduced between two already existing airports, or conversely, underused flights might be removed. In the neural network example, network evolution means the ontogenesis of the hippocampal structure. In other words, the evolution of a network involves the addition and/or deletion of edges and vertices. We intend to model these kinds of phenomena, by using a discrete time, stochastic framework. We are particularly interested in the inverse problem: what is the best description of the evolution of a given network, or set of networks, in a well-defined mathematical framework? This is a data-driven approach; one can even interpret it as experimental science: we make experiments on the networks to see how they behave, although our possibilities are often quite limited. For example we cannot change the flight time of an “edge” just to see how the network will react. If, however, such an event has already happened for some particular reason, we are able to observe one possible reaction. Put a different way, in our approach the input is the data collected about the evolution of a network, the output is a set of parameters for a stochastic model framework. In our case, the parameters are so-called kernel functions. This chapter is organized as follows. First, we define the stochastic kernel-based framework in Sect. 2 and formalize the inverse problem. In Sect. 3 we show two methods for estimating kernel functions, the frequentist and the maximum likelihood methods. In Sect. 4 we show some possible applications of the methodology.
Source Publication
Handbook of Large-Scale Random Networks
Source Editors/Authors
Béla Bollobás, Robert Kozma, Dezsö Miklós
Publication Date
2008
Recommended Citation
Csárdi, Gábor; Strandburg, Katherine J.; Tobochnik, Jan; and Érdi, Péter, "The Inverse Problem of Evolving Networks—with Application to Social Nets" (2008). Faculty Chapters. 1679.
https://gretchen.law.nyu.edu/fac-chapt/1679
