Search

In this paper, we look at content placement in the high-dimensional regime: there are $$n$$ servers, and $${\mathrm {O}}(n)$$ distinct types of content. Each server can store and serve $${\mathrm {O}}(1)$$ types at any given time. Demands for these content types arrive and have to be served in an online fashion; over time, there are a total of $${\mathrm {O}}(n)$$ of these demands. We consider the algorithmic task of content placement: determining which types of content should be on which server at any given time, in the setting where the demand statistics (i.e., the relative popularity of each type of content) are not known a-priori, but have to be inferred from the very demands we are trying to satisfy. This is the high-dimensional regime because this scaling (everything being $${\mathrm {O}}(n)$$ ) prevents consistent estimation of demand statistics; it models many modern settings where large numbers of users, servers, and videos/webpages interact in this way. We characterize the performance of any scheme that separates learning and placement (i.e., which uses a portion of the demands to gain some estimate of the demand statistics, and then uses the same for the remaining demands), showing it is order-wise strictly suboptimal. We then study a simple adaptive scheme-which myopically attempts to store the most recently requested content on idle servers-and show it outperforms schemes that separate learning and placement. Our results also generalize to the setting where the demand statistics change with time. Overall, our results demonstrate that separating the estimation of demand, and the subsequent use of the same, is strictly suboptimal. [ABSTRACT FROM AUTHOR]

The process by which new ideas, innovations, and behaviors spread through a large social network can be thought of as a networked interaction game: Each agent obtains information from certain number of agents in his friendship neighborhood, and adapts his idea or behavior to increase his benefit. In this paper, we are interested in how opinions, about a certain topic, form in social networks. We model opinions as continuous scalars ranging from 0 to 1 with 1 ( 0 ) representing extremely positive (negative) opinion. Each agent has an initial opinion and incurs some cost depending on the opinions of his neighbors, his initial opinion, and his stubbornness about his initial opinion. Agents iteratively update their opinions based on their own initial opinions and observing the opinions of their neighbors. The iterative update of an agent can be viewed as a myopic cost-minimization response (i.e., the so-called best response) to the others’ actions. We study whether an equilibrium can emerge as a result of such local interactions and how such equilibrium possibly depends on the network structure, initial opinions of the agents, and the location of stubborn agents and the extent of their stubbornness. We also study the convergence speed to such equilibrium and characterize the convergence time as a function of aforementioned factors. We also discuss the implications of such results in a few well-known graphs such as Erdos–Renyi random graphs and small-world graphs. [ABSTRACT FROM AUTHOR]

For a wireless network with n nodes distributed in an area A, and with n source-destination pairs communicating with each other at some common rate, the hierarchical cooperation scheme proposed in (Ozgur, Leveque, and Tse, 2007) is analyzed and optimized by choosing the number of hierarchical stages and the corresponding cluster sizes that maximize the total throughput. It turns out that increasing the number of stages does not necessarily improve the throughput, and the closed-form solutions for the optimization problem can be explicitly obtained. Based on the expression of the maximum achievable throughput, it is found that the hierarchical scheme achieves a scaling with the exponent depending on n. In addition, to apply the hierarchical cooperation scheme to random networks, a clustering algorithm is developed, which divides the whole network into quadrilateral clusters, each with exactly the number of nodes required. [ABSTRACT FROM AUTHOR]