ABSTRACT
CONTENTS 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Composite Graph Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Composite Stretch Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Theoretical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.2 Composite Stretch of Some Special Graphs . . . . . . . . . . . . . . . . 10 1.3.3 Average vs. Worst-Case Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Composite Broadcast Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5 Composite Betweenness Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.1 Constrained Composite Load on Path Graphs . . . . . . . . . . . . . . . 17 1.5.2 Composite Centrality in Manhattan Grid Networks . . . . . . . . . 17
1.6 Multicast in Composite Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.6.2 Hierarchy-Compliant Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.6.3 Algorithms for H-Compliant Multicast . . . . . . . . . . . . . . . . . . . . . 21
1.7 Simulation-Based Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.7.1 Chain of Command . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.7.1.1 Evaluation of Basic Composite Network Metrics 28 1.7.1.2 Evaluation of Composite Network Multicast . . . . 30
1.7.2 Friend-of-a-Friend (FOAF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.8 Conclusion and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.1 Introduction The recent explosive growth in online social networks has been fueled by the proliferation of high-speed and highly available communication networks such as the Internet and broadband cellular wireless networks, as well as the increasing popularity of mobile network-ready devices such as “smartphones” and tablets. People tend to share information with other people they know, who subsequently forward that information along various links in the social network-this occurs either verbatim (for example, the directives from a commander flow through the chain of command) or after modifications (for example, propagation of rumors, gossip, or news on Twitter). A social network’s topology thus constrains or guides the flow and spread of information through it. These constraints can force the information to traverse much longer paths in the underlying communication network between its originator and its ultimate consumers. This phenomenon, known as stretch, is justified because the intermediaries may play a critical role in interpreting or modifying the information or they may serve as important links in the acquaintance chain, without whom the originator and the ultimate consumers would not have known each other.
