Preferential attachment models have been widely studied in complex networks, because they can explain the formation of many networks like social networks, citation networks, power grids, and biological networks, to name a few. Motivated by the application of key predistribution in wireless sensor networks (WSN), we initiate the study of preferential attachment with degree bound. Our paper has two important contributions to two different areas. The first is a contribution in the study of complex networks. We propose preferential attachment model with degree bound for the first time. In the normal preferential attachment model, the degree distribution follows a power law, with many nodes of low degree and a few nodes of high degree. In our scheme, the nodes can have a maximum degree @math , where @math is an integer chosen according to the application. The second is in the security of wireless sensor networks. We propose a new key predistribution scheme based on the above model. The important features of this model are that the network is fully connected, it has fewer keys, has larger size of the giant component and lower average path length compared with traditional key predistribution schemes and comparable resilience to random node attacks. We argue that in many networks like key predistribution and Internet of Things, having nodes of very high degree will be a bottle-neck in communication. Thus, studying preferential attachment model with degree bound will open up new directions in the study of complex networks, and will have many applications in real world scenarios.
Blackburn and Gerke @cite_1 studied . The problem is to attach a list of @math colors to each of @math nodes, the colors being chosen uniformly at random from a set of @math colors, such that two nodes are connected if they have a common color in their list. It can be seen that EG network is an example of these types of graphs. They analyzed the connectivity of such graphs.
@cite_1
2008111483
A uniform random intersection graphG(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks, in particular when modelling the network graph of the well-known key predistribution technique due to Eschenauer and Gligor. The paper determines the threshold for connectivity of the graph G(n,m,k) when n-> in many situations. For example, when k is a function of n such that k>=2 and [email protected]?n^@[email protected]? for some fixed positive real number @a then G(n,m,k) is almost surely connected when lim infk^2n mlogn>1, and G(n,m,k) is almost surely disconnected when lim supk^2n mlogn<1.