Impact of Social Relation and Group Size in Multicast Ad Hoc Networks

上游充通大 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

Previous Works Motivation 上浒充通大￥ The theory of social networks:social features SHANGHAI JIAO TONG UNIVERSITY Social feature ll social relation The social relation reflects how users select friends in the network.From the experiments in [9][10]about how people selected friends,some feasible social relation models are proposed such as distance-based model [9]and rank-based model [10]. [9]B.Azimdoost,H.Sadjadpour,J.Garcia-Luna-Aceves,"The Impact of Social Groups on The Capacity of Wireless Networks,"in Network Science Workshop,pp.30-37,2011. [10]R.Kumar,D.Liben-Nowell,et.al,"Theoretical Analysis of Geographic Routing in Social Networks,"in MIT-CSAIL- TR-2005-040,Jun.2005. 6

Previous Works & Motivation The theory of social networks: social features ➢ Social feature II : social relation 6 The social relation reflects how users select friends in the network. From the experiments in [9] [10] about how people selected friends, some feasible social relation models are proposed such as distance-based model [9] and rank-based model [10]. [9] B. Azimdoost, H. Sadjadpour, J. Garcia-Luna-Aceves, “The Impact of Social Groups on The Capacity of Wireless Networks,” in Network Science Workshop, pp. 30-37, 2011. [10] R. Kumar, D. Liben-Nowell, et.al, “Theoretical Analysis of Geographic Routing in Social Networks,” in MIT-CSAIL￾TR-2005-040, Jun. 2005

Previous Works Motivation 上浒充通大学 The importance of multicast study SHANGHAI JIAO TONG UNIVERSITY What is multicast? One source to m destinations 00 a ● O o 0 a Xiangyang Li [11] [11]X.Li,"Multicast Capacity of Large Scale Wireless Ad Hoc Networks",IEEE/ACM Trans.Networking,Vol.17,No. 3,pp.950-961,Jan.2008.(citation:132) 7

Previous Works & Motivation The importance of multicast study ➢ What is multicast? One source to m destinations 7 Xiangyang Li [11] [11] X. Li, “Multicast Capacity of Large Scale Wireless Ad Hoc Networks”, IEEE/ACM Trans. Networking, Vol.17, No. 3, pp. 950-961, Jan. 2008.(citation:132)

Previous Works Motivation 上浒充通大￥ The multicast uses SHANGHAI JIAO TONG UNIVERSITY Video sources Video clients Live Video distribution ntemet and mobile networks Collaborative groupware Periodic Data Delivery- Stock quotes,sports scores, "Push"technology magazines,newspapers,adverts Hub site Any Applications with Server/Web-site multiple receivers replication (1-to-many) Branch Branch office Branch office office Resource Discovery Reducing Network/ more than multiple Resource Overhead point-to-point flows Distributed Interactive Wargames,virtual reality Simulation (DIS) 8

Previous Works & Motivation The multicast uses 8 Any Applications with multiple receivers (1-to-many) Collaborative groupware Reducing Network/ Resource Overhead Live Video distribution Server/Web-site replication Resource Discovery Periodic Data Delivery – "Push" technology Stock quotes, sports scores, magazines, newspapers, adverts more than multiple point-to-point flows Distributed Interactive Simulation (DIS) Wargames, virtual reality Video sources Internet and mobile networks Video clients Hub site Branch office Branch office Branch office

Previous Works Motivation 上浒充通大 Our view on the multicast social networks SHANGHAI JIAO TONG UNIVERSITY According to the mentioned theory of social networks and multicast,we can conclude the relation between social features and multicast as follow: The social group size determines the multicast scale. The social relation determines the distribution of multicast destinations. The social features (social group size and relation)determine the network features(multicast scale and destination distribution)and further impact the network performance such as capacity. We investigate the impact of social features on network capacity in this paper. 9

Previous Works & Motivation Our view on the multicast social networks ➢ According to the mentioned theory of social networks and multicast, we can conclude the relation between social features and multicast as follow: ✓ The social group size determines the multicast scale. ✓ The social relation determines the distribution of multicast destinations. 9 We investigate the impact of social features on network capacity in this paper. ➢ The social features (social group size and relation) determine the network features (multicast scale and destination distribution) and further impact the network performance such as capacity

Previous Works Motivation 上浒充通大￥ Main challenge and contribution SHANGHAI JIAO TONG UNIVERSITY Multicast group size Power-law This work distribution (Social network based) 1 Fixed Multicast Start point group size destination (X.Li's work [11]) distribution Uniform Rank-based model distribution (Social network based) 10

Previous Works & Motivation Main challenge and contribution 10 Start point (X. Li’s work [11]) Multicast group size Multicast destination distribution Fixed group size Uniform distribution This work Power-law distribution Rank-based model (Social network based) (Social network based)