A Caltech Library Service

Network Effects in Small Networks: A Study of Cooperation


Noorzad, Parham (2017) Network Effects in Small Networks: A Study of Cooperation. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9M32STV.


Communication over a point-to-point link is relatively well understood. However, when such a link is part of a larger network, our understanding is far from complete. Nonetheless, progress in this area has important consequences in both the theoretical and practical aspects of communication networks.

In this work, we focus on the role of a single link in networks that in addition to point-to-point links, contain "multi-terminal components." An example of a network consisting of a single multi-terminal component is the uplink in a wireless communication network where multiple transmitters communicate with a single receiver over a shared medium. We demonstrate the existence of a class of such networks where a finite capacity link results in a rate gain for each source that far exceeds the capacity of that link. This is an example of a "network effect": the phenomenon where a resource, here link capacity, is significantly more valuable in a network than in isolation. Here we measure the "value" of the finite capacity link by the sum-capacity gain per source that it enables.

The central idea behind the construction of networks that exhibit such effects is the introduction of a node, referred to as the "cooperation facilitator" (CF), that allows other network nodes to work together to reduce interference. In the setting of the classical multiple access channel (MAC), an example of a CF is a node that receives rate-limited information from each transmitter and broadcasts rate-limited information back to the transmitters through a common bottleneck link. Let the "cooperation rate" be the capacity of the CF bottleneck link. We show that for a class of MACs, the presence of a CF leads to a sum-capacity gain that, as a function of the cooperation rate, has an infinite slope at cooperation rate zero. This means that the bottleneck link of the CF is significantly more valuable in some networks than in isolation. This class of MACs includes well-known examples such as the Gaussian MAC and the binary adder MAC.

In addition to sum-capacity gain, cooperation under the CF model also improves reliability. Specifically, in the case of the MAC with two transmitters, whenever the CF has full access to both messages, the maximal- and average error capacity regions coincide. This effect is observed even when the cooperation rate is "negligible"; that is, the cooperation rate grows sublinearly in the number of channel uses. An implication of this result is the existence of a network whose maximal-error sum-capacity is not continuous with respect to the capacities of its edges; this means that in some networks, even a negligible cooperation rate leads to a positive sum-capacity gain.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Capacity Region; Communication Networks; Cooperation Facilitator; Edge Removal; Multiple Access Channel; Network Information Theory; Network Effects; Reliability; Sum-Capacity; Transmitter Cooperation
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Effros, Michelle
Thesis Committee:
  • Effros, Michelle (chair)
  • Langberg, Michael
  • Bruck, Jehoshua
  • Hassibi, Babak
  • Kostina, Victoria
  • Ligett, Katrina A.
Defense Date:22 May 2017
Funding AgencyGrant Number
National Science Foundation1321129
National Science Foundation1527524
National Science Foundation1526771
National Science Foundation1018741
National Science Foundation1038578
National Science Foundation0905615
Record Number:CaltechTHESIS:06062017-101123885
Persistent URL:
Related URLs:
URLURL TypeDescription adapted for Chapter 2 adapted for Chapter 3 adapted for Chapter 5
Noorzad, Parham0000-0002-0201-3791
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10299
Deposited By: Parham Noorzad
Deposited On:07 Jun 2017 21:23
Last Modified:04 Oct 2019 00:16

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page