Network realization
Networks are used in all aspects of life to represent the interconnections among groups of individuals or entities of different kinds. Every network has many different measurable attributes. For example, we can measure the number of connections each entity has in the network (referred to as its degree). This research direction concerns the problem of designing networks to satisfy a given set of requirements, referred to as a specification. In our degree example, we may consider the following problem. Given a list of n numbers (viewed as a degree specification), design a network with n entities, such that their degrees are equal to the numbers in the list. Such a network is said to realize the given specification. Many other types of measures can be used for the specification. As one more example, given an n-by-n table of numbers, we may want to design a network with the entities 1, 2, ..., n so that the distance between a pair of entities i and j equals to the number in entry (i,j) of the table.
We study research questions related to realizability of network specifications. Besides the fundamental theoretical interest in understanding the feasibility and cost of network realization, our study is also practically motivated, as networks (e.g., communication, information, social, and transportation networks) are prevalent in all aspects of our lives, and the need to design networks tailored to specific requirements is on the rise.