Accession Number:



Network Characteristics and Dynamics: Reciprocity, Competition and Information Dissemination

Descriptive Note:

[Technical Report, Doctoral Thesis]

Corporate Author:

Cornell UniversityUniversity of Massachusetts Amherst College of Information and Computer Sciences

Personal Author(s):

Report Date:


Pagination or Media Count:



Networks are commonly used to study complex systems. This requires a good understanding of structural characteristics and evolution dynamics of networks, and their impacts on a variety of dynamic processes taking place on top of them. In this thesis, we study various aspects of network characteristics and dynamics, with a focus on reciprocity, competition and information dissemination. We first formulate the maximum reciprocity problem and study its use in the interpretation of reciprocity in real networks. We propose to interpret reciprocity based on its comparison with maximum possible reciprocity for a network exhibiting the same degrees. We show maximum reciprocity problem is NP-hard, and use an upper bound instead of the maximum. We find this bound is surprisingly close to the empirical reciprocity in a wide range of real networks, and there is via surprisingly strong linear relationship between the two. We show that certain small suboptimal motifs called 3-paths are the major cause for suboptimality. Secondly, we analyze competition dynamics under cumulative advantage, where accumulated resource promotes gathering even more resource. We characterize the tail distributions of duration and intensity for pairwise competition. We show that duration always has a power-law tail irrespective of competitors fitness, while intensity has either a power-law tail or an exponential tail depending on competitors fitness. We observe a struggle-of-the-fitness phenomenon, where a slight different in fitness results in an extremely heavy tail of duration distribution. Lastly, we study the efficiency of information dissemination in social networks with limited budget of attention. We quantify the efficiency of information dissemination for both cooperative and selfish user. We identify topologies where cooperation plays a critical role in efficient information propagation. We propose an incentive mechanism called plus-one to coax users into cooperation in such cases.

Subject Categories:

  • Operations Research

Distribution Statement:

[A, Approved For Public Release]