(466d) The Construction of Networks with Prescribed Collective Properties

Porous media exhibit network topologies and attempts to study such materials have naturally focused on this structural feature [1,2]. Network theory has also been used extensively to model systems in other fields ranging from social sciences to biology [3-5]. Our understanding of the dynamic behavior of these systems relies on predicting the evolution of network topology [6-8]. A promising approach to developing models for network evolution relies on using the equation-free framework [9], which focuses on suitable coarse observables of the system and then identifies an appropriate way to lift, or transform, from the coarse description to the full description of the system. For certain problems with simple dynamical evolution, using the degree distribution and the mean clustering coefficient as the coarse variables successfully reduces the system dynamics. However, for other dynamical evolution problems like those of social networks [10], we find that relying merely on these metrics does not convey enough information about the state of the system. In such cases, one has to resort to using more detailed descriptions of the network, such as the degree-dependent clustering coefficient (or, equivalently, degree-dependent number of triangles), to be included in the set of coarse variables and, to do so, knowledge of sample graphs that possess given degree-dependent clustering is required. The necessity for constructing a network, or graph, with prescribed collective properties presents us with an interesting combinatorial problem. So far, methods for constructing such graphs [11-14] have focused on the randomness of their results and the adherence to certain distributions of interest, with no explicit guarantees of achieving the prescribed properties exactly or within bounded deviations. Moreover, none of the existing methods addresses the requirement for certain degree-dependent number of triangles. To that end, we have developed a novel approach based on a rigorous mathematical programming formulation that can construct graphs that are guaranteed to possess the desired properties. Properties supported by the formulation include the degree distribution, the overall clustering coefficient (global or mean), and the degree-dependent number of triangles. The method uses well-established Mixed-Integer Linear Programming (MILP) solution techniques [15,16] and is capable of identifying one, multiple or even all ?when reasonable to do so? networks that possess the desired properties. Additional properties, such as the similarity to a given network, can also be accommodated by the formulation. In cases when there is no guarantee that the prescription is feasible, it typically suffices to look for solutions that satisfy the desired within appropriate upper and lower bounds. One of the major challenges of a pure Mathematical Programming approach is the problem's large combinatorial complexity, which makes instances with even a small number of nodes to be intractable for off-the-shelf commercial optimization software. In order to address such a challenge, we have devised an iterative preprocessing step to rank-order the set of possible arcs in terms of their likelihood to participate in feasible solutions. Then, in a subsequent iterative scheme, we take decisions on which of those arcs we could a-priori postulate as part of the solution. Postulating the existence of certain arcs, that is, postulating a sub-graph to be part of our final solution, reduces the size of the MILP formulation and brings the remaining problem ?which is of significantly smaller complexity than the original? within the capabilities of state-of-the-art optimization software. The overall scheme inherits the exactness of the MILP solution algorithm and can thus guarantee the identification of a solution, when one exists, in all cases. Computational experiments demonstrate the effectiveness of the approach and its suitability to serve the various applications that require the knowledge of networks with given properties.

[1] Constantinides G.N. and A.C. Payatakes. ?Network simulation of steady-state two-phase flow in consolidated porous media?. AIChE Journal 42(2):369-382 (1996).

[2] Tsakiroglou C.D. and A.C. Payatakes. ?Characterization of the pore structure of reservoir rocks with the aid of serial sectioning analysis, mercury porosimetry and network simulation?. Advances in Water Resources 23:773-789 (2000).

[3] Newman M.E.J. "The structure and function of complex networks". SIAM Review 45(2):167-256 (2003).

[4] Colizza V, A. Flammini, A. Maritan and A. Vespignani. ?Characterization and modeling of protein-protein interaction networks?. Physica A 352(1):1-27 (2005).

[5] Newman M.E.J., D.J. Watts and S.H. Strogatz. "Random graph models of social networks". Proceedings of the National Academy of Sciences 99:2566-2572 (2002).

[6] Dorogovtsev S.N. and J.F.F. Mendes. ?The evolution of networks: From biological nets to the Internet and WWW?. Oxford University Press, Oxford (2003).

[7] Barrat A.M., M. Barthelemy and A. Vespignani. ?Dynamical processes on complex networks?. Cambridge University Press, New York, NY, USA (2008).

[8] Newman M.E.J., A.L. Barabasi and D.J. Watts. ?The structure and dynamics of networks?. Princeton University Press, Princeton, NJ, USA (2006).

[9] Kevrekidis I.G., C.W. Gear and G. Hummer. "Equation-free: The computer-aided analysis of complex multiscale systems". AIChE Journal 50(7):1346-1355 (2004).

[10] Davidsen J., H. Ebel and S. Bornholdt. "Emergence of a small world from local interactions: Modeling acquaintance networks?. Physical Review Letters 88(12) (2002).

[11] Newman M.E.J. ?Properties of highly clustered networks?. Physical Review E 68 (2003).

[12] Volz E. ?Random networks with tunable degree distribution and clustering?. Physical Review E 70 (2004).

[13] Serrano M.A. and M. Boguna. ?Tuning clustering in random networks with arbitrary degree distributions? Physical Review E 72 (2005).

[14] Bansal S., S. Khandelwal and L.A. Meyers. ?Exploring biological network structure with clustered random networks?. BMC Bioinformatics 10 (2009).

[15] Nemhauser G.L. and L.A. Wolsey. ?Integer and combinatorial optimization?. Wiley, New York, NY, USA (1998).

[16] Floudas C.A. ?Nonlinear and mixed-integer optimization: Fundamntals and applications?. Oxford University Press, New York, NY, USA (1995).