Impact of Social Relation and Group Size in Multicast Ad Hoc Networks.pdf_大学文库

Impact of Social Relation and Group Size in Multicast Ad Hoc Networks Yi Qin,Riheng Jia,Jinbei Zhang,Weijie Wu,Xinbing Wang Abstract-This paper investigates the multicast capacity of The second characteristic of social networks is the social static wireless social networks.We adopt the two-layer network relation which has been studied for more than thirty years model,which includes the social layer and the networking layer. [9].[16]-[19].In 1979.the authors in [16]focused on about In the social layer,the social group size of each source node is modeled as power-law distribution.Moreover,the rank-based 500 persons in a network.Further research about 130 million model is utilized to describe the relation between source and persons of Myspace was demonstrated in [17].In their works, destinations in the networking layer.Based on the two-layer the social network was modeled as a graph to describe the network model,the probability density function (PDF)of the geographical and social relations among users.Moreover,the destination positions is analyzed and verified by numerical sim- social relation in these papers reflected how users select friends ulation,which is different from the traditional ad hoc networks According to the PDF,the bound of the network capacity is in the network,and it was usually determined by the factors derived,and we propose a Euclidean minimum spanning tree such as friendship,common interest or alliance,which was based transmission scheme,which is proved to achieve the order different from the traditional ad hoc networks.From the above of capacity bound for most cases.Finally,the capacity of social studies of the experiments about how people selected friends, networks is compared with the traditional multicast ad hoc some feasible social relation models were proposed such as networks,which indicates that the capacity scaling performs better in social networks than traditional ones.To our best distance-based model and rank-based model [19].The scaling knowledge,this is the first work of analyzing the impact on laws of these two models were analyzed in [9]and [18], the capacity of social relation and group size in multicast ad hoc respectively.In [9],the probability that node j was a friend of networks for the rank-based model. node i was proportional to d(i,j)-,where d(i,j)represented the distance between i and j.Instead,in [18],the authors I.INTRODUCTION illustrated that the probability was proportional to Rank(j), where Ranki(j)was the rank of j with respect to i. Network scaling law was firstly studied by Gupta and The two social characteristics above were both observed Kumar [1],followed by many works about the network through statistics from online social networks.However,they capacity and throughput [2]-[4].However,their models fell can also be introduced into wireless networks because that short in well characterizing real social networks,and they they are independent from the wireless nature of the networks. had to consider simplified models instead.For example,in Moreover,it is worthwhile to study wireless social networks most of these works,the destinations associated with each due to the two facts:1)The study of wireless social networks is user were drawn according to a uniform distribution,which is promising for the reason that the social wireless networks,such unrealistic.To give another example,it was also an unrealistic as MSN wireless client,facebook wireless client.have gained a assumption that the number of friends was known apriori large popularity nowadays.Furthermore,in cellular networks, in traditional multicast ad hoc networks [2]-[4].Therefore, as the number of wireless terminals increases,one base- many researchers turned to study social characteristics such station needs to service more and more terminals.However, as the way people selected friends (destinations)[5][6]and the number of simultaneously serviced terminals is restricted the number of these friends [7][8].It was only recently that due to the limited up-link resource.This will reduce the studying social phenomena had become a hot topic in ad per-terminal throughput when there are too many terminals. hoc networks [9],peer to peer networks [10]and some other Therefore,wireless multi-hop transmission can be adopted to networks [11]-[14]. improve the per-terminal throughput of social networks.2)The To study the social phenomenon.two characteristics of multi-hop user relaying technology has become an important social networks are considered in our paper,which are the topic and been well studied.It can be demonstrated from [201. social group size and the social relation.Firstly,we introduce which investigated coordination among users through wireless the group size which describes the number of friends for each channel (such as multi-hop),that the user relaying technology node.In [7][8][15],the authors analyzed the probability that helped to improve the capacity of wireless system. an arbitrary node had g friends based on the data of Cyworld, Additionally,the nodes in the network need to transmit their MySpace and orkutwith,each with more than 10 million users. packets to all of their friends by multicasting in this paper, The results showed that the probability satisfied the power-law which is also a common requirement.For example,a user of distribution.which generally matched the fact. facebook may want to send a message to all of his friends. The capacity of traditional multicast ad hoc networks was The authors are with the Department of Electronic Engineering Shanghai Jiao Tong University,China intensively studied in [2]-[4].However,the traditional results Email:[qinyi_33,jiariheng,abelchina,weijiewu,xwang8)@sjtu.edu.cn cannot be directly applied to social networks,and therefore

1 Impact of Social Relation and Group Size in Multicast Ad Hoc Networks Yi Qin, Riheng Jia, Jinbei Zhang, Weijie Wu, Xinbing Wang Abstract—This paper investigates the multicast capacity of static wireless social networks. We adopt the two-layer network model, which includes the social layer and the networking layer. In the social layer, the social group size of each source node is modeled as power-law distribution. Moreover, the rank-based model is utilized to describe the relation between source and destinations in the networking layer. Based on the two-layer network model, the probability density function (PDF) of the destination positions is analyzed and verified by numerical simulation, which is different from the traditional ad hoc networks. According to the PDF, the bound of the network capacity is derived, and we propose a Euclidean minimum spanning tree based transmission scheme, which is proved to achieve the order of capacity bound for most cases. Finally, the capacity of social networks is compared with the traditional multicast ad hoc networks, which indicates that the capacity scaling performs better in social networks than traditional ones. To our best knowledge, this is the first work of analyzing the impact on the capacity of social relation and group size in multicast ad hoc networks for the rank-based model. I. INTRODUCTION Network scaling law was firstly studied by Gupta and Kumar [1], followed by many works about the network capacity and throughput [2]- [4]. However, their models fell short in well characterizing real social networks, and they had to consider simplified models instead. For example, in most of these works, the destinations associated with each user were drawn according to a uniform distribution, which is unrealistic. To give another example, it was also an unrealistic assumption that the number of friends was known apriori in traditional multicast ad hoc networks [2]- [4]. Therefore, many researchers turned to study social characteristics such as the way people selected friends (destinations) [5] [6] and the number of these friends [7] [8]. It was only recently that studying social phenomena had become a hot topic in ad hoc networks [9], peer to peer networks [10] and some other networks [11]- [14]. To study the social phenomenon, two characteristics of social networks are considered in our paper, which are the social group size and the social relation. Firstly, we introduce the group size which describes the number of friends for each node. In [7] [8] [15], the authors analyzed the probability that an arbitrary node had q friends 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. The authors are with the Department of Electronic Engineering Shanghai Jiao Tong University, China Email: {qinyi 33, jiariheng, abelchina, weijiewu, xwang8}@sjtu.edu.cn The second characteristic of social networks is the social relation which has been studied for more than thirty years [9], [16]- [19]. In 1979, the authors in [16] focused on about 500 persons in a network. Further research about 130 million persons of Myspace was demonstrated in [17]. In their works, the social network was modeled as a graph to describe the geographical and social relations among users. Moreover, the social relation in these papers reflected how users select friends in the network, and it was usually determined by the factors such as friendship, common interest or alliance, which was different from the traditional ad hoc networks. From the above studies of the experiments about how people selected friends, some feasible social relation models were proposed such as distance-based model and rank-based model [19]. The scaling laws of these two models were analyzed in [9] and [18], respectively. In [9], the probability that node j was a friend of node i was proportional to d(i, j) −α, where d(i, j) represented the distance between i and j. Instead, in [18], the authors illustrated that the probability was proportional to Rank−α i (j), where Ranki(j) was the rank of j with respect to i. The two social characteristics above were both observed through statistics from online social networks. However, they can also be introduced into wireless networks because that they are independent from the wireless nature of the networks. Moreover, it is worthwhile to study wireless social networks due to the two facts: 1) The study of wireless social networks is promising for the reason that the social wireless networks, such as MSN wireless client, facebook wireless client, have gained a large popularity nowadays. Furthermore, in cellular networks, as the number of wireless terminals increases, one basestation needs to service more and more terminals. However, the number of simultaneously serviced terminals is restricted due to the limited up-link resource. This will reduce the per-terminal throughput when there are too many terminals. Therefore, wireless multi-hop transmission can be adopted to improve the per-terminal throughput of social networks. 2) The multi-hop user relaying technology has become an important topic and been well studied. It can be demonstrated from [20], which investigated coordination among users through wireless channel (such as multi-hop), that the user relaying technology helped to improve the capacity of wireless system. Additionally, the nodes in the network need to transmit their packets to all of their friends by multicasting in this paper, which is also a common requirement. For example, a user of facebook may want to send a message to all of his friends. The capacity of traditional multicast ad hoc networks was intensively studied in [2]- [4]. However, the traditional results cannot be directly applied to social networks, and therefore

3 we present this paper to improve and generalize the theory II.NETWORK MODEL AND DEFINITIONS of ad hoc network capacity.In particular,the main differ- In this section,the two-layer model of static social networks ence between the social networks and the traditional ad hoc is proposed based on group size and social relation,which networks is the Probability Distribution Function (PDF)of are the main differences between social network model and destination positions.Therefore,a challenging question arises traditional ad hoc network model.Moreover,we also list some when considering the two social characteristics: network performance metrics and notations for our following How do the two characteristics of static social networks analysis. jointly impact the capacity of network,and what is the capacity achieving scheme? A.The Social Network Model To answer this question,we study the two-layer static social network model,which includes social layer and networking In this paper,we adopt the two-layer network model,which layer.In the social layer,the social group size of each source includes node was modeled as power-law distribution model.Moreover, 1)Social layer:This layer captures the social relation the rank-based model was utilized to describe the relation among individuals,which is not related with the network between source and destinations in the networking layer.For topology. a node with g friends,the PDF of its friends'positions 2)Networking layer:This layer reflects the network topol- are derived in our paper.The simulations of the PDF are ogy based on the node positions. also illustrated.which verify the theoretical results.We then In the social layer,each node i selects some friends as its analyze the bound of network capacity and propose a capacity destinations,which form a social group.Moreover,the size of achieving scheme based on the Euclidean Minimum Spanning the social group,denoted as gi.is proved to satisfy the power- Tree. law degree distribution in [9].In particular,the experiments The main contributions of this paper are summarized as of three online social networking services,each with more follows: than 10 million users,indicate that P[qi=g}follows the The relation between rank and geographical position of an distribution in (1) arbitrary node is demonstrated for rank-based static social 1 network model.If there are n nodes in the network which Plqi=q)=Gng5 (1) is of size 1 x 1,the result shows that =e (V n with probability 1 when n goes to infinity,where z is where B≥0 is a constant and Gn=∑a 1 g=1 g8 the distance between source and destination.Moreover. In the networking layer,we consider the network which is we also derive the PDF of the destination positions for a a unit square,and n static nodes (users)are uniformly and randomly distributed in it.The well-known protocol model as given source,which is verified by the simulations. We analyze the capacity bound of the social network in [1]is employed as the interference model in our network. model based on the PDF of destination positions and When node i wants to transmit a packet to node j.the Euclidean Minimum Spanning Tree.Moreover,a corre- transmission is considered to be successful if the following sponding transmission scheme is proposed to achieve the inequality is satisfied capacity bound in most cases. lIXi-Xl≤r(n), (2) Finally,we compare the capacity of social networks with the traditional ad hoc networks,and the results where Xi represents node i's location,and r(n)is the max- indicate that the capacity scaling performs better in social imum transmission range of each node,which is a function networks than traditional ad hoc networks. of n.here is the Euclidean distance.Moreover,any other The rest of this paper is organized as follows.In Section node k who wants to transmit packet at the same time must II,we introduce the network model and definitions.The PDF satisfy the inequality as of destination positions and the capacity bound of the social IXk-X‖≥(1+△)r(n) (3) network model are derived in Section III,and the theoretical results of the PDF is verified by numerical simulations in Sec- where A>0 is a constant factor depending on the acceptable tion IV.In Section V,a capacity achieving scheme is proposed Signal to Interference Noise Ratio (SINR)of the network to demonstrate that the capacity is achievable in most cases.In Furthermore,the bandwidth of the network is finite and Section VI,we compare the capacity of social networks with constant.In this model,the transmission range r(n)is assumed traditional ad hoc networks.Finally,we conclude in Section asr(n)[1].which guarantees the connectivity of VIl. the network.In addition,each node transmits packet to its destinations through multi-hop. IWe use standard asymptotic notations in our paper.Consider t wo nonnegative function f()and g():(1)f(n)=o(g(n)) It is important to study the node mapping from the social means limnoo f(n)/g(n)=0.(2)f(n)= O(g(n))mean- layer to the networking layer.We adopt the rank-based model s limnoo f(n)/g(n)0.(5)f(n)=e(g(n))means f(n)=O(g(n)) and g(n)=O(f(n)).(6)f(n)=e(g(n))means that there exists two con- selected with probability PBased on social experiments stants a and b satisfy f(n)=O(g(n)loga n)and f(n)=(g(n)log n) [19],the friends of a user are more likely to be close to him

2 we present this paper to improve and generalize the theory of ad hoc network capacity. In particular, the main difference between the social networks and the traditional ad hoc networks is the Probability Distribution Function (PDF) of destination positions. Therefore, a challenging question arises when considering the two social characteristics: • How do the two characteristics of static social networks jointly impact the capacity of network, and what is the capacity achieving scheme? To answer this question, we study the two-layer static social network model, which includes social layer and networking layer. In the social layer, the social group size of each source node was modeled as power-law distribution model. Moreover, the rank-based model was utilized to describe the relation between source and destinations in the networking layer. For a node with q friends, the PDF of its friends’ positions are derived in our paper. The simulations of the PDF are also illustrated, which verify the theoretical results. We then analyze the bound of network capacity and propose a capacity achieving scheme based on the Euclidean Minimum Spanning Tree. The main contributions of this paper are summarized as follows: • The relation between rank and geographical position of an arbitrary node is demonstrated for rank-based static social network model. If there are n nodes in the network which is of size 1 × 1, the result shows that x = Θ ✏➮Rank n ✑ 1 with probability 1 when n goes to infinity, where x is the distance between source and destination. Moreover, we also derive the PDF of the destination positions for a given source, which is verified by the simulations. • We analyze the capacity bound of the social network model based on the PDF of destination positions and Euclidean Minimum Spanning Tree. Moreover, a corresponding transmission scheme is proposed to achieve the capacity bound in most cases. • Finally, we compare the capacity of social networks with the traditional ad hoc networks, and the results indicate that the capacity scaling performs better in social networks than traditional ad hoc networks. The rest of this paper is organized as follows. In Section II, we introduce the network model and definitions. The PDF of destination positions and the capacity bound of the social network model are derived in Section III, and the theoretical results of the PDF is verified by numerical simulations in Section IV. In Section V, a capacity achieving scheme is proposed to demonstrate that the capacity is achievable in most cases. In Section VI, we compare the capacity of social networks with traditional ad hoc networks. Finally, we conclude in Section VII. 1We use standard asymptotic notations in our paper. Consider two nonnegative function f(·) and g(·): (1) f(n) = o(g(n)) means limn→∞ f(n)/g(n) = 0. (2) f(n) = O(g(n)) means limn→∞ f(n)/g(n) 0. (5) f(n) = Θ(g(n)) means f(n) = O(g(n)) and g(n) = O(f(n)). (6) f(n) = Θ( ˜ g(n)) means that there exists two constants a and b satisfy f(n) = O(g(n) loga n) and f(n) = Ω(g(n) logb n) II. NETWORK MODEL AND DEFINITIONS In this section, the two-layer model of static social networks is proposed based on group size and social relation, which are the main differences between social network model and traditional ad hoc network model. Moreover, we also list some network performance metrics and notations for our following analysis. A. The Social Network Model In this paper, we adopt the two-layer network model, which includes 1) Social layer: This layer captures the social relation among individuals, which is not related with the network topology. 2) Networking layer: This layer reflects the network topology based on the node positions. In the social layer, each node i selects some friends as its destinations, which form a social group. Moreover, the size of the social group, denoted as qi , is proved to satisfy the powerlaw degree distribution in [9]. In particular, the experiments of three online social networking services, each with more than 10 million users, indicate that P{qi = q} follows the distribution in (1) P{qi = q} = 1 Gnq β , (1) where β ≥ 0 is a constant and Gn = Pn q=1 1 q β . In the networking layer, we consider the network which is a unit square, and n static nodes (users) are uniformly and randomly distributed in it. The well-known protocol model as in [1] is employed as the interference model in our network. When node i wants to transmit a packet to node j, the transmission is considered to be successful if the following inequality is satisfied kXi − Xjk ≤ r(n), (2) where Xi represents node i’s location, and r(n) is the maximum transmission range of each node, which is a function of n. k · k here is the Euclidean distance. Moreover, any other node k who wants to transmit packet at the same time must satisfy the inequality as kXk − Xjk ≥ (1 + ∆)r(n), (3) where ∆ > 0 is a constant factor depending on the acceptable Signal to Interference Noise Ratio (SINR) of the network. Furthermore, the bandwidth of the network is finite and constant. In this model, the transmission range r(n) is assumed as r(n) = √ log n √ n [1], which guarantees the connectivity of the network. In addition, each node transmits packet to its destinations through multi-hop. It is important to study the node mapping from the social layer to the networking layer. We adopt the rank-based model in [18] and [19]. In this model, for a given node i, when it selects one friend from all the nodes, we denote that node j is selected with probability Pi→j . Based on social experiments [19], the friends of a user are more likely to be close to him

Denoting P as the set consisting all the nodes and d(i,j)= TABLE I:Important Definitions of Symbols and Notations Xi-Xill as the distance between i and j,the rank of j with Symbol Definition respect to i is defined as N Number of users Ranki(j)=k EP:d(i,k)0 is a constant.When a =0,the network is the fn(x,θ) The probability density function of destina- traditional ad hoc network.(5)shows the fact that a node is tion positions more likely to select a friend that nearby.Furthermore,this EMST The total length of the EMST model focuses on relative location instead of geographic lo- C(n) The capacity of the network cation.We defineHTherefore,by normalizing. Na(n) The minimum total number of hops for a (5)can be represented as multicast tree with g+1 nodes The capacity ratio of social networks and 1 P=H.Rank (j) (6 Ra traditional ad hoc networks when each node has q friends In [19],the authors verify the (6)by online data.It should be noticed that we consider the case that one node selects multiple destinations instead of one.Therefore,the distribution of the destinations will be analyzed based on both social group size Thus,in order to minimize the length of transmission path,the and (6). Euclidean Minimum Spanning Tree (EMST)is investigated. The total length for this EMST is proved in [21]to satisfy the B.Network Performance Metrics and Notations following lemma. We give the definitions of throughput and capacity in this Lemma 1 Let f(x)denote the PDF of the related nodes in subsection.Moreover,some notations are also demonstrated. Definition of throughput:For a given scheme,we define the the network,where x is the position vector.Then,for large number of nodes n and the network dimension d 1,if f(x) throughput as the maximum achievable transmission rate.In t time slots,any i's destination (denoted as k)receives Mi(k,t) is independent from n,the total length for the EMST satisfies packets and the number of i's friends is qi.The long term per-node throughput of this multicast session is defined by 照EMST可=d网f学k, (9) (n)as(n)=liminf(t).Then the average with probability 1,where c(d)is constant. throughput of this scheme is defined by T(n) The proof of this lemma is demonstrated in [21],and d=2 in our paper.However,when f(x)is related with n,Lemma T(n)=liminf二>λ(n) (7)1 does not hold.As a result,we denote the PDF as fr(x)in this paper and give the following lemma which indicates the Definition of capacity:In this social network,C(n)is said bound of the total length of the EMST for infinite n. to be the asymptotic per-node social multicast capacity with order e(To(n)),where To(n)satisfies (8). Lemma 2 If fn(x)in Lemma I is related with infinite n and the following two conditions are satisfied, T(n) (Tw:io问 =0∞}=0， (8) 。Condition I:There exists a function gn(x）= T(n) {Tm):imo简 >0}≠0， ∑e:ewTile:satisfying for any feasible T(n). lgn(x）-fn(x)ldx→0， (10) Furthermore,we list some important parameters in Table I that will be used in later analysis,proofs and discussions. when n goes to infinity,where is the range of total network,Ei(i=l,2,·）is the partition of业separating III.CAPACITY ANALYSIS FOR SOCIAL NETWORKS 亚into many nor-overlapping parts(i.e,ξi∩ξj=0,i≠ In this section,firstly,the relation between rank and ge- jand Ei=亚，lξ：is an indicative function and ographical position of an arbitrary node is analyzed.Based egn(x)dx=Je fn(x)dx.Moreover,each part Ei is a on such relation,we derive the PDF of the destinations,and d-dimensional hypercube,and the number of its adjacent finally obtain the bound of capacity. parts is limited by a constant The links between the nodes belonging to one multicast Condition 2:lim ngn(x)dx=(1)with probabil- n+0 session are considered,which can organize a spanning tree. ity 1

3 Denoting P as the set consisting all the nodes and d(i, j) = kXi − Xjk as the distance between i and j, the rank of j with respect to i is defined as Ranki(j) = |{k ∈ P : d(i, k) 0} 6= ∅, (8) for any feasible T(n). Furthermore, we list some important parameters in Table I that will be used in later analysis, proofs and discussions. III. CAPACITY ANALYSIS FOR SOCIAL NETWORKS In this section, firstly, the relation between rank and geographical position of an arbitrary node is analyzed. Based on such relation, we derive the PDF of the destinations, and finally obtain the bound of capacity. The links between the nodes belonging to one multicast session are considered, which can organize a spanning tree. TABLE I: Important Definitions of Symbols and Notations Symbol Definition n Number of users r(n) The maximum transmission range qi Number of destinations (friends) of user i α Parameter of rank-based model β Parameter of power-law distribution of group size Ranki(j) The rank of j with respect to i fn(x, θ) The probability density function of destination positions kEMSTk The total length of the EMST C(n) The capacity of the network Nq(n) The minimum total number of hops for a multicast tree with q + 1 nodes Rq The capacity ratio of social networks and traditional ad hoc networks when each node has q friends Thus, in order to minimize the length of transmission path, the Euclidean Minimum Spanning Tree (EMST) is investigated. The total length for this EMST is proved in [21] to satisfy the following lemma. Lemma 1 Let f(x) denote the PDF of the related nodes in the network, where x is the position vector. Then, for large number of nodes n and the network dimension d > 1, if f(x) is independent from n, the total length for the EMST satisfies limn→∞ n − d−1 d kEMSTk = c(d) ❩ Rd f(x) d−1 d dx, (9) with probability 1, where c(d) is constant. The proof of this lemma is demonstrated in [21], and d = 2 in our paper. However, when f(x) is related with n, Lemma 1 does not hold. As a result, we denote the PDF as fn(x) in this paper and give the following lemma which indicates the bound of the total length of the EMST for infinite n. Lemma 2 If fn(x) in Lemma 1 is related with infinite n and the following two conditions are satisfied, • Condition 1: P There exists a function gn(x) = ξi∈Ψ γi1ξi satisfying ❩ Ψ |gn(x) − fn(x)|dx → 0, (10) when n goes to infinity, where Ψ is the range of total network, ξi(i = 1, 2, · · ·) is the partition of Ψ separating Ψ into many non-overlapping parts (i.e., ξi∩ξj = ∅, ∀i 6= j and ❙ ξi = Ψ), 1ξi is an indicative function and ❘ ξi gn(x)dx = ❘ ξi fn(x)dx. Moreover, each part ξi is a d-dimensional hypercube, and the number of its adjacent parts is limited by a constant ζ. • Condition 2: limn→∞ n ❘ ξi gn(x)dx = Ω(1) with probability 1

4 One than has that with probability 1 limn→∞ n −d−1 d kEMSTk ❘ Rd fn(x) d−1 d dx = c(d), (11) where c(d) is constant. Proof: The proof can be found in the Appendix. Moreover, according to the sum of p-series, the Gn in (1) and Hn in (6) can be represented as Hn = ❳n i=1 1 i α = ✽ ❁ ✿ Θ n 1−α ✁ 0 ≤ α 1, (12) and Gn = ❳n q=1 1 q β = ✽ ❁ ✿ Θ n 1−β ✁ 0 ≤ β 1. (13) To calculate the PDF of user i’s qi friends, the relation between rank and geographical position is important. We will show this relation in Lemma 4 which is supported by Lemma 3. It should be noticed that the impact of boundary effect on scaling laws can be ignored in the proofs of this paper, which can also be found in other works of scaling laws [2]. Lemma 3 We denote two constants a and b where 0 1. For any X ∈ {1, 2, · · · , n}, there must be n! X!(n − X)! ✏ aX n ✑X ✏ 1 − aX n ✑n−X 1 is constant, and (a) holds due to the fact that lim n→∞ ⑨n e ❾n √ 2πn n! = 1. (17) Moreover, for any c > 0, there must be 1 2e. The P ✏ x ≤ ➮aX n ✑ satisfies P ✒ x ≤ ➱ aX πn ✓ = ❳n k=X P(There are k nodes within ➱ aX πn away from node i) = ❳n k=X n! k!(n − k)!( aX n ) k (1 − aX n ) n−k . (20) Denoting g(k) = n! k!(n−k)!( aX n ) k (1 − aX n ) n−k , based on Lemma 3, there must be g(X) k + 1 aX . (21) Thus, for any k > X, g(k) satisfies g(k) < aX k g(k − 1) < · · · < (aX) k−XX! k! g(X). (22) Therefore, P ✏ x ≤ ➮aX n ✑ in (19) can be upper-bounded as P ✒ x ≤ ➱ aX πn ✓ < ❳n k=X (aX) k−XX! k! g(X) (a) < c3 ❳n k=X (aX) k−X X e ✁X √ X k e ✁k √ k g(X) = c3 ❳n k=X ✏ aXe k ✑k ✏ 1 ae✑X ➱ X k g(X) < c3g(X) ❳n k=X (ae) k−X < 2c3g(X), (23) (a) holds due to (17). For P ✏ x ≥ ➮bX πn ✑ , we denote g ∗ (k) = n! k!(n−k)!( bX n ) k (1 − bX n ) n−k and P ✏ x ≥ ➮bX πn ✑ < 2c3g ∗ (k) can be proved in the similar way as above. Hence, the probability that the distance between node i and j does not satisfy x = Θ ✏➮X n ✑ can be represented as 1 − P ✒ x = Θ ✒➱ X n ✓✓ < 2c3c1(ae 1−a ) X + 2c3c2(be1−b ) X. (24)

It should be noticed that ci(ael-a)x and c2(bel-b)x are Denoting C(X,qi,n)as the monotonic functions of a and b with lower-bound 0. respectively.For any given constant c>0,there must exist a 0,4 and b satisfying cac1(ael-a)X+c3c2(be1-6)xcqi).We arbitrarily select two integers Xa and X.Based on (32)and C(X,gi,n)X> To derive the fn(x)in Lemma 2,we first show the distri- c4qi we can obtain bution of rank of i's friends when it has gi friends in the next Lemma.Afterwards,we derive the PDF in Theorem 1 based 0X1X2,91十 0X1X2a-1>c4 OX1X3.9-1X1X29-2 X9 Xe X9X8 on the relation between rank and geographical position. ,xg+三之c4 0x,4=+9-2 X X X9X9 Lemma 5 If i is a source node with qi destinations,and j is (34) one of them.The probability that Ranki(j)=X satisfies If c.can be lower-bounded as y P{Rank:()=X}=日 qi+nl-axa (26) 0x1X2,44> C-1)ax-1)ox (35) 2X9 2X9 when0≤acan be lower-bounded as when a =1 and Ci(qi,n)is given in (45),and 0x4-1>50E40a2 (36 0X1X2,4-1 1 P{Rank()=X}=日 gi+qi-axa (28) Therefore,the relation between and can be derived as when a>1. 0X1X2,94-1> C50X1X2,4:0X1X2,9-2 Proof:We sort the nodes based on the rank respects X1X2,94-1 to i as v,·,vn-l,where Rank(vx）=X.The set of = C50x1X9X1X2,9-2 X9 X1X2,94-1 (37 destinations of i is denoted as Qi,where Qi=gi.Therefore, X the probability that Ranki(j)=X is cs(c4-1)0x1X,g-2 P{Rank:()=X}=P{i=UXUX∈Q}P{vx∈Q}, X (29) Thus,we calculate the bound of C(X1,qi,n)as follows which is shown in [9].In particular,PjxQ)= and Pfvx EQi}can be represented as C(X19:,n)=9 3,+e X x-1+巴 1 H Xo 94:0X1X24 (38) P{vx∈Q}= 1≤1<<ig-1≤n,h≠Xh=1 (ad-可+10xx9- 1 1 1≤ii<…<ig:≤nh=1 C(X1,9,n)< (s-+)g:0x1da4 (30) 0X1X2,4t-1 We define ox.q-1- Therefore,it is obvious that 1i1<…<g4-1≤n,h≠Xh C(X1,9,n)=9 40xX1X29L) (39) 0X1X2,4-1 l≤i1<…<ig,≤nh=1 Similarly, C(X2,qi,n)=曰 90X1X2:44 =日(C(X1,q,n), (40) 1≤i1<… 0X1X2,44-1 which means that the order of C(X,gi,n)is independent from X when C(X,qi,n)=w(gi).Hence,we denote (31) C(X,qi,n)as cxC(qi,n)where cx may be related to X,qi

5 It should be noticed that c1(ae1−a ) X and c2(be1−b ) X are the monotonic functions of a and b with lower-bound 0, respectively. For any given constant c > 0, there must exist a and b satisfying c3c1(ae1−a ) X +c3c2(be1−b ) X 1. Proof: We sort the nodes based on the rank respects to i as v1, · · · , vn−1, where Ranki(vX) = X. The set of destinations of i is denoted as Qi , where |Qi | = qi . Therefore, the probability that Ranki(j) = X is P{Ranki(j) = X} = P{j = vX|vX ∈ Qi}P{vX ∈ Qi}, (29) which is shown in [9]. In particular, P{j = vX|vX ∈ Qi} = 1 qi and P{vX ∈ Qi} can be represented as P{vX ∈ Qi} = 1 HnXα P 1≤i1 c4qi). We arbitrarily select two integers Xa and Xb. Based on (32) and C(X, qi , n)Xα > c4qi we can obtain σX1X2,qi + σX1X2,qi−1 Xα 2 > c4 ⑩σX1X2,qi−1 Xα 1 + σX1X2,qi−2 Xα 2 Xα 1 ❿ , σX1X2,qi + σX1X2,qi−1 Xα 1 > c4 ⑩σX1X2,qi−1 Xα 2 + σX1X2,qi−2 Xα 2 Xα 1 ❿ . (34) If c4 > 1, σX1X2,qi can be lower-bounded as σX1X2,qi > (c4 − 1)σX1X2,qi−1 2Xα 2 + (c4 − 1)σX1X2,qi−1 2Xα 1 . (35) According to the Newton’s inequality in [22] that for any constant c5 > 0, σX1X2,qi−1 can be lower-bounded as σX1X2,qi−1 > c5σX1X2,qi σX1X2,qi−2 σX1X2,qi−1 . (36) Therefore, the relation between σX1X2,qi−1 and σX1X2,qi−2 Xα 2 can be derived as σX1X2,qi−1 > c5σX1X2,qi σX1X2,qi−2 σX1X2,qi−1 = c5 Xα 2 σX1X2,qi σX1X2,qi−2 σX1X2,qi−1 Xα 2 > c5(c4 − 1)σX1X2,qi−2 Xα 2 . (37) Thus, we calculate the bound of C(X1, qi , n) as follows C(X1, qi, n) = qi σX1X2,qi + σX2X2,qi−1 Xα 2 σX1X2,qi−1 + σX1X2,qi−2 Xα 2 > qiσX1X2,qi ⑨ 1 c5(c4−1) + 1❾ σX1X2,qi−1 , C(X1, qi, n) < ⑨ 1 c5(c4−1) + 1❾ qiσX1X2,qi σX1X2,qi−1 . (38) Therefore, it is obvious that C(X1, qi, n) = Θ( qiσX1X2,qi σX1X2,qi−1 ). (39) Similarly, C(X2, qi, n) = Θ ✒ qiσX1X2,qi σX1X2,qi−1 ✓ = Θ(C(X1, qi, n)), (40) which means that the order of C(X, qi , n) is independent from X when C(X, qi , n)Xα = ω(qi). Hence, we denote C(X, qi , n) as cXC(qi , n) where cX may be related to X, qi

7 where c 0 X is the upper-bound of c 0 X, which equals to 2. Hence, fn(x, θ) = Θ( n qi ) is proved when qi = ω(nx2α). Moreover, if qi = O(nx2α), after some similar mathematical manipulations, the fn(x, θ) can be represented as fn(x, θ) = Θ x −2α ✁ . (56) Consequently, the PDF for 0 ≤ α 1, the expectation of the bound kEMSTk in (11) satisfies kEMSTk = ✽ ❃❃❃❃❃❁ ❃❃❃❃❃✿ O q α i n 1−α ✁ qi = O(n α−1 α ), 1 r. The number of destinations in this region is lower-bounded as ❩ ξ fn(x, θ)dξ > qi 2 ❩ r d 0 ❩ d+ r 2 d− r 2 xfn(x, θ)dxdθ = c8qir 2 d 2C1(qi , n) , (61) where d ≥ ➮ qi nC1(qi,n) , and 1 8π r because qi = ω(log n) = ω(C1(qi , n)). Since d > r and r ∝ d α, there are at most 2 α + 1 adjacent parts at each side of ξi . Considering the fact that ξi has only 4 sides, the ζ in the Theorem 2 is no greater than 2 α+2 + 4, which is a constant. Thus the Conditions in Lemma 2 are satisfied. Similarly, the Conditions in Lemma 2 also hold in the case 0 ≤ α 1, and we do not show it in the following proof for brevity. We define gn(x, θ) = 1 r 2 ❘ ξ xfn(x, θ)dxdθ when (x, θ) is in ➮ ξ, where ξ is a square region with side length r. If d ≥ qi nC1(qi,n) , the difference between gn(x, θ) and fn(x, θ) in ξ can be derived as ❩ ξ |fn(x, θ) − gn(x, θ)|dξ < ❩ r d 0 ❩ d+ r 2 d− r 2 |fn(x, θ) − gn(x, θ)|xdxdθ = c9r 3 d 3C1(qi, n) , (63) where 1 8π < c9 < 1 π is constant. Thus, according to (53) and (55), the condition 1 of Lemma 2 can be proved as follow ❩ Ψ |fn(x, θ) − gn(x, θ)|dξ = ❩ 2π 0 ❩ 1 ➮ qi nC1(qi ,n) |fn(x, θ) − gn(x, θ)|xdxdθ + ❩ 2π 0 ❩ ➮ qi nC1(qi ,n) 0 |fn(x, θ) − gn(x, θ)|xdxdθ (a) < ❳ d 2πd r ❩ r d 0 ❩ d+ r 2 d− r 2 |fn(x, θ) − gn(x, θ)|xdxdθ + ❩ 2π 0 ❩ ➮ qi nC1(qi ,n) 0 c1(ae1−a ) X0+1(c 0 X + c 0 X)n 2πc 0 Xc 0 Xqi xdxdθ < ❳ d 2πc9r 2 d 2C1(qi, n) + c1(ae1−a ) X0+1(c 0 X + c 0 X) c 0 Xc 0 X , (64) (a) holds because there are less than 2πd r regions with side length r and d from the source. Moreover, considering the relation between d and r in (62) and the maximum value of d is 1 2 , (64) can be bounded by ❳ d 2πc9r 2 d 2C1(qi, n) + c1(ae1−a ) X0+1(c 0 X + c 0 X) c 0 Xc 0 X < 4πc9 log n ♣ c8qiC1(qi, n) + c1(ae1−a ) X0+1(c 0 X + c 0 X) c 0 Xc 0 X =o(1). (65) Therefore, the two conditions in Lemma 2 are satisfied. We denote that x † = ➮ qi nC1(qi,n) and the kEMSTk is as kEMSTk <c10c(d) √ qi ❩ 2π 0 ❩ 1 0 x ➱ n qi + nC1(qi, n)x2 dxdθ <2c10c(d)π √ qi ✧❩ x † 0 x √ n √qi dx + ❩ 1 x† ➱ 1 C1(qi, n) dx★ <2c10c(d)π ➱ qi C1(qi, n) , (66)

8 where c10 is constant according to the proof of Theorem 1. Similarly, (67) can also be proved. kEMSTk > c10c(d)π 2 ➱ qi C1(qi, n) , (67) where c10 is constant according to Theorem 1. Thus, kEMSTk = Θ ✏➮ qi C1(qi,n) ✑ . If qi = Θ(1), (11) cannot be applied. However, the kEMSTk is upper-bounded by the sum distance between i and its qi friends and lower-bounded by the distance between i and one of its friends. Therefore, the order of kEMSTk can be expressed as kEMSTk = Θ ⑩ 1 log n ❿ . (68) If qi = ω(1) and qi = O(log n), it is obvious that the two conditions in Lemma 2 cannot be satisfied simultaneously based on (61) to (65). Therefore, (11) cannot be adopted in this case, and we give the upper-bound of kEMSTk as follow kEMSTk = O ⑩ qi log n ❿ , (69) which is the sum length of qi direct links. Consequently, equation (58) is proved. Case 2: 0 ≤ α r. Similar to the proof of case 1, the two conditions in Lemma 2 are satisfied for the region x ⑨ qi n ❾ 1 2α . The number of destinations in the region with side length r and d > ⑨ qi n ❾ 1 2α is lower-bounded by qi 2 ❩ r d 0 ❩ d+ r 2 d− r 2 xfn(x, θ)dxdθ = c11qir 2 d 2α , (70) where 1 8π r, i.e., d > (c11qi) 1 2α−2 . We define gn(x, θ) = 1 r 2 ❘ ξ xfn(x, θ)dxdθ, where ξ is a square region with side length r. Thus, if (c11qi) 1 2α−2 ⑨ qi n ❾ 1 2α , we will propose another PDF f 0 n (x, θ), which satisfies the two conditions and its corresponding kEMSTk is the same as fn(x, θ) in order sense. The number of destinations within the ring ⑨ qi n ❾ 1 2α 1 > 2π(c11) 2−α α−1 q 1 2α−2 i 1−α , the order of kEMSTk of fn(x, θ) and f 0 n (x, θ) are the same. Consequently, kEMSTk for fn(x, θ) is the same as f 0 n (x, θ) in order sense for the case 0 1. We try to find when the two conditions in Lemma 2 are satisfied first. The network is also separated into some small square regions as above. Therefore, the number of destinations in one region ξ and d > ➮qi n is lower-bounded as qi ❩ r d 0 ❩ d+ r 2 d− r 2 xfn(x, θ)dxdθ > c12q α i r 2 d 2αnα−1 , (74) where 1 8π r which indicates that d n α−1 α , it can be proved in the similar way as in (63) to (65) that ❩ Ψ |fn(x, θ) − gn(x, θ)|dξ = o(1). (75) Hence, when qi > n α−1 α , the two conditions in Lemma 2 are satisfied. and the kEMSTk can be calculated by (11). However, if qi q α 2α−2 i√ n , where c13 → 1 when n → ∞. According to (63) to (65), it can be

9 found that the nodes in group 1 satisfy condition 1 and 2 in simultaneously.In our network model,the number of nodes Lemma 2.Thus,the EMST for group 1 can be calculated in a region with side length r(n)is e(log n).Thus,the relation based on Lemma 2.Then we derive f(,0)as between N(n)and EMST]is fn(r,0) %ifn(z,0) EMST Na(n)= and Ng(n)= EMSTI z,了点e0tr0 C14 (77 r(n) r(n)log n (82) Vn due to the 'hop reduction'.To obtain the order of N(n),we for x and fa(,)=0 for Vn,where give the following lemma. c14>0 is constant according to Theorem 1.The number of destinations in group 2 is Lemma 6 The expectation of the minimum total number of 2 hops for a multicast tree satisfies fn(,0)drde 1. (80) Proof:Firstly,we prove the lemma under the condition when q=(n).Moreover,the total EMSTII must be that a =1.Considering a square region with side length greater than the lEMSTIl of nodes within the range of r(n),which is kr(n)away from the source,when the total from the center. Therefore,the EMSTI is lower-bounded number of destinations is q,the expectation of the number of by destinations in this region can be upper-bounded as k+)√四 EMSTI>c(d)v屈 x2fn(,0) -dxd0. DkC:(am)logn' Di satisfies Consequently,according to (80)and (81),the EMSTII is r(k+1)√ Dk1,which is shown in Section VI,we use e() instead of e()here and ignore the poly-logarithmic factors. where ci5 is constant according to Theorem 1.If kV高，which means8a<1,here 2c1691 can transmit to multiple nodes simultaneously if the distance between them are smaller than r(n).Thus,these hops can is no hop reduction.Moreover,ifk<√C(og，元the be treated as one,and we denote this as 'hop reduction'. number of 'hop reduction'is smaller than vlogn in each For example,if there are ko destinations distributed in a region with side length r(n).Finally,the total number of 'hop small region with side length less than r(n)uniformly and reduction'is the sum of the two parts,i.e.o independently,the total length of the EMST among them is r(n)ko which consists at least ko hops.But the total hop and o minwhere 2c169 for them is 1 since the source can transmit to other nodes is the maximum value of k.Thus,according to (87). 2/log n

9 found that the nodes in group 1 satisfy condition 1 and 2 in Lemma 2. Thus, the kEMSTk for group 1 can be calculated based on Lemma 2. Then we derive f (2) n (x, θ) as f (2) n (x, θ) = fn(x, θ) ❘ 2π 0 ❘ 1 q α 2α−2 i√n xfn(x, θ)dxdθ > qifn(x, θ) c14 , (77) for x > q α 2α−2 i√ n , and f2(x, θ) = 0 for x 0 is constant according to Theorem 1. The number of destinations in group 2 is qi ❩ 2π 0 ❩ 1 q α 2α−2 i√n xfn(x, θ)dxdθ c(d) √ qi ❩ 2π 0 ❩ √ √ qi n 0 ❒ x2fn(x, θ) ❘ 2π 0 ❘ √ √ qi n 0 xfn(x, θ)dxdθ dxdθ. (81) Consequently, according to (80) and (81), the kEMSTk is summarized in (60). Moreover, since the capacity ratio of social networks and traditional ad hoc networks is greater than Θ(1) ˜ when α > 1, which is shown in Section VI, we use Θ( ˜ ·) instead of Θ(·) here and ignore the poly-logarithmic factors. Denoting the expectation of the minimum total number of hops for a multicast tree is Nq(n). If the packet is transmitted through the path which is close to the line of multicast tree within Θ ✏➮log n n ✑ , the order of the total length of the path equals to kEMSTk in order sense. However, another important case must be considered, which is that one node can transmit to multiple nodes simultaneously if the distance between them are smaller than r(n). Thus, these hops can be treated as one, and we denote this as ‘hop reduction’. For example, if there are k0 destinations distributed in a small region with side length less than r(n) uniformly and independently, the total length of the EMST among them is r(n) √ k0 which consists at least k0 hops. But the total hop for them is 1 since the source can transmit to other nodes simultaneously. In our network model, the number of nodes in a region with side length r(n) is Θ(log n). Thus, the relation between Nq(n) and kEMSTk is Nq(n) = O ✒ kEMSTk r(n) ✓ , and Nq(n) = Ω ✒ kEMSTk r(n) log n ✓ , (82) due to the ‘hop reduction’. To obtain the order of Nq(n), we give the following lemma. Lemma 6 The expectation of the minimum total number of hops for a multicast tree satisfies Nq(n) = ✽ ❁ ✿ Θ ✏ kEMST k r(n) ✑ q = o ⑨ n log n log log n ❾ , Θ˜ ✏ kEMST k r(n) ✑ q = Ω ⑨ n log n log log n ❾ , (83) where α = 1, and Nq(n) = ✽ ❁ ✿ Θ ✏ kEMST k r(n) ✑ q = o ⑨ n log n ❾ , Θ˜ ✏ kEMST k r(n) ✑ q = Ω ⑨ n log n ❾ , (84) where 0 ≤ α 1. Proof: Firstly, we prove the lemma under the condition that α = 1. Considering a square region with side length r(n), which is kr(n) away from the source, when the total number of destinations is q, the expectation of the number of destinations in this region can be upper-bounded as Dk ➮ q C1(q,n) log n , Dk satisfies Dk q 2c15q C1(q,n) , which means 2c15qi k2C1(q,n) < 1, there is no ‘hop reduction’. Moreover, if k < ➮ q C1(q,n) log n , the number of ‘hop reduction’ is smaller than √ log n in each region with side length r(n). Finally, the total number of ‘hop reduction’ is the sum of the two parts, i.e., k < ➮ q C1(q,n) log n and ➮ q C1(q,n) log n < k < min➜q 2c15q C1(q,n) , √ n 2 √ log n ➟ , where √ n 2 √ log n is the maximum value of k. Thus, according to (87)

10 the total number of ‘hop reduction’ is upper-bounded by π √ log nq C1(q, n) log n + min♥➮ 2c15q C1(q,n) , √n 2 √log n ♦ ❳ k= ♣ q C1(q,n) log n 4c15πq kC1(q, n) C1(q,n)n 8c15 log n . (89) Furthermore, when q c10c(d)π 2 ➱ qn C1(q, n) log n > 4c15πq log 2c15 log n C1(q, n) , (90) when n goes to infinite. Hence, the ‘hop reduction’ can be ignored in this condition in order sense. Consequently, according to (82), the expectation of the minimum total number of hops for a multicast tree is as in (83) when α = 1. Similarly, the expectation of the minimum total number of hops for the case 0 ≤ α 1 can be derived, and the results are demonstrated in (84) and (85), respectively. According to Lemma 6, the capacity bound of this social network model can be derived in the following theorem. Theorem 3 The expectation of the capacity of this social network model is bounded by C(n) = ✽ ❃❁ ❃✿ Θ˜ 1 n ✁ 0 ≤ β ≤ 1, Θ˜ n β−2 ✁ 1 3 2 , (91) when 0 ≤ α 2, (92) when α = 1, and C(n) = Θ˜ ✒ 1 E{kEMSTk}√ n ✓ , (93) when α > 1, and E{kEMSTk} = Pn q=1 kEMSTk q βGn . We do not show the detailed expressions for the sake of conciseness. Proof: From Lemma 6, we know that the total number of hops is Nq(n) for each multicast session. Therefore, the expectation of the total number of hops is E{Nq(n)} = Pn q=1 Nq(n) q βGn . Furthermore, there are n multicast sessions in the network. Since the transmission range is limited by r(n), there are at most 1 r 2(n) active nodes in one time slot in average. Thus, the capacity of the network is bounded by 1 E{Nq(n)}nr2(n) = 1 E{Nq(n)} log n . (94) The capacity bound can be calculated based on Theorem 2, and the results are presented in (91), (92) and (93). IV. SIMULATIONS In this section, we will give simulations about the destination PDFs for the source which has q destinations. In our simulations, the number of nodes n is from 1×104 to 1×105 , and the number of destinations is q = n 4 5 . The distance range is 0 ≤ x ≤ 1. The simulation results are averaged over 10000 realizations. For each realization, firstly, n nodes are randomly and uniformly distributed in the network, and we assume that the source is at the center of the network. Afterwards, q destinations are selected based on the rank-based model in (6). Finally, the statistical PDF of these nodes is obtained and compared with the theoretical result. The statistical PDF is obtained according to the simulation results. On the other hand, the corresponding theoretical PDF is fn(x) = 2πxfn(x, θ), which can be expressed as fn(x) = ✽ ❃❃❃❁ ❃❃❃✿ Θ ✏ n 1 5 x 1+n 1 5 x2α ✑ 0 ≤ α 1 (95) In our simulation, we use Surface Fitting to obtain the simulation results. Therefore, based on (95), we give the equation of surface fitting method as follows fn(x) = ✽ ❃❁ ❃✿ a1n b1 x c3 1+d1ne1 xf1 0 ≤ α 1 (96) where ai to gi are the surface fitting parameters. In our simulations, we only focus on bi , ci , ei , fi and gi to show the order of the PDF. The simulation results are illustrated in Figure 1 for the case 0 ≤ α < 1, and α is assumed to be 0.5 here. Moreover, 0 0.2 0.4 0.6 0.8 1 0 2 4 6 8 10 x 104 Distance x n PDF Fig. 1: The comparison of theoretical PDF and statistical PDF for α = 0.5. the corresponding parameters are given in Table II. R-square in Table II is the coefficient of determination. If R-square is close to 1, it means that the fitting is accurate. From the simulation