上游充通大 SHANGHAI JIAO TONG UNIVERSITY Impact of Social Relation and Group Size in Multicast Ad Hoc Networks Yi Qin,Riheng Jia,Jinbei Zhang, Weijie Wu,Xinbing Wang Shanghai Jiao Tong University
Impact of Social Relation and Group Size in Multicast Ad Hoc Networks Yi Qin, Riheng Jia, Jinbei Zhang, Weijie Wu, Xinbing Wang Shanghai Jiao Tong University
Outline 上浒充通大学 SHANGHAI JIAO TONG UNIVERSITY ▣Introduction >Previous works Motivation System model and main idea The capacity upper-bound of multicast social networks The capacity achieving scheme ▣Discussion Conclusion and future directions 2
2 Outline ❑ Introduction ➢ Previous works & Motivation ❑ System model and main idea ❑ The capacity upper-bound of multicast social networks ❑ The capacity achieving scheme ❑ Discussion ❑ Conclusion and future directions
Previous Works Motivation 上浒充通大粤 Social networks SHANGHAI JIAO TONG UNIVERSITY > Social networks Each user has multiple friends. The friends of each user are selected according to some factors such as friendship,common interest or alliance. The user transmits information to some or all of its friends. 3
Previous Works & Motivation Social networks ➢ Social networks 3 ✓ Each user has multiple friends. ✓ The friends of each user are selected according to some factors such as friendship, common interest or alliance. ✓ The user transmits information to some or all of its friends
Previous Works Motivation 上浒充通大￥ Social networks SHANGHAI JIAO TONG UNIVERSITY The history of social networks[1] In the late 1890s,Ferdinand Tonnies and Emile Durkheim propose the idea of social networks in their theories and research of social groups [2]. √ Afterwards,major works about social networks can be found by several groups in psychology,anthropology,and mathematics working independently [3][4]. Nowadays,social networks are widely studied based on the online social networks with millions of persons [5][6]. [1]Wikipedia:social network.http://en.wikipedia.org/wiki/Social_network. [2]Tonnies,Ferdinand(1887).Gemeinschaft und Gesellschaft,Leipzig:Fues's Verlag.(Translated,1957 by Charles Price Loomis as Community and Society,East Lansing:Michigan State University Press.) [3]Scott,John P.,"Social Network Analysis:A Handbook(2nd edition)",Thousand Oaks,CA:Sage Publications, 2000. [4]Peter J.Scott,John,"The Sage Handbook of Social Network Analysis",2011. [5]Y.Ahn,S.Han,H.Kwak,S.Moon,H.Jeong,"Analysis of topological characteristics of huge online social networking services,"in 16th intemational conference on World Wide Web,New York,USA,pp.835-844,2007. [6]D.Liben-Nowell,J.Novak,R.Kumar,P.Raghavan,A.Tomkins,R.Graham,"Geographic routing in social networks,"in Proceedings of the National Academy of Sciences of the United States of America,vol.102,no.33,pp. 11623-11628,2005
Previous Works & Motivation Social networks ➢ The history of social networks[1] 4 ✓ In the late 1890s, Ferdinand Tönnies and Émile Durkheim propose the idea of social networks in their theories and research of social groups [2]. ✓ Afterwards, major works about social networks can be found by several groups in psychology, anthropology, and mathematics working independently [3] [4]. ✓ Nowadays, social networks are widely studied based on the online social networks with millions of persons [5] [6]. [1] Wikipedia: social network. http://en.wikipedia.org/wiki/Social_network. [2] Tönnies, Ferdinand (1887). Gemeinschaft und Gesellschaft, Leipzig: Fues's Verlag. (Translated, 1957 by Charles Price Loomis as Community and Society, East Lansing: Michigan State University Press.) [3] Scott, John P., ”Social Network Analysis: A Handbook (2nd edition)”, Thousand Oaks, CA: Sage Publications, 2000. [4] Peter J. & Scott, John, “The Sage Handbook of Social Network Analysis”, 2011. [5] Y. Ahn, S. Han, H. Kwak, S. Moon, H. Jeong, “Analysis of topological characteristics of huge online social networking services,” in 16th international conference on World Wide Web, New York, USA, pp. 835-844, 2007. [6] D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins, R. Graham, “Geographic routing in social networks,” in Proceedings of the National Academy of Sciences of the United States of America, vol. 102, no. 33, pp. 11623-11628, 2005
Previous Works Motivation 上浒充通大 The theory of social networks:social features SHANGHAI JIAO TONG UNIVERSITY Social feature I:social group The social group size describes the number of friends for each user.In [5][7][8], the authors analyzed the distribution of social group size based on the data of Cyworld,MySpace and orkutwith,each with more than 10 million users.The results showed that the probability satisfied the power-law distribution,which generally matched the fact. [7]P.Fraigniaud,G.Giakkoupis,"The effect of power-law degrees on the navigability of small worlds,"In Proc.28th ACM Symposium on Principles of Distributed Computing,pp 240-249,2009 [8]J.Kleinberg,"The small-world phenomenon:an algorithm perspective,"in 32nd Annual ACM Symposium on Theory of Computing,Portland,Oregon,USA,May 2000. 5
Previous Works & Motivation The theory of social networks: social features ➢ Social feature I : social group 5 The social group size describes the number of friends for each user. In [5] [7] [8], the authors analyzed the distribution of social group size based on the data of Cyworld, MySpace and orkutwith, each with more than 10 million users. The results showed that the probability satisfied the power-law distribution, which generally matched the fact. [7] P. Fraigniaud, G. Giakkoupis, “The effect of power-law degrees on the navigability of small worlds,” In Proc. 28th ACM Symposium on Principles of Distributed Computing, pp 240-249, 2009. [8] J. Kleinberg, “The small-world phenomenon: an algorithm perspective,” in 32nd Annual ACM Symposium on Theory of Computing, Portland, Oregon, USA, May 2000