The PLNGen Algorithm

© 2005 LIRIS Lyon - Pascal BIHLER

The PLNGen algorithm generates efficiently "Pseudo Local Network" structures. Pseudo Local Networks normaly have several local and a few distant connections. Based on a number of random decision and designed with the goal of creating complex structures with a non-complex algorithm, they neither reflect correctly natural computer nor Small-World networks. Nevertheless, these networks can be used to simulate on a very low level heterogenious, partially connected networks (like networks of pervasive entities) formed with local network-mediums like WLAN or Bluetooth.
The algorithm has a run-time complexity of O(n) as well as a memory complexity of O(n).

The main idea of the algorithm is to distribute normally the network nodes on a area of fixed size. While distributing the nodes, connections with backConnDistance d predecessors are established. For each node, the connectivity c_i (c_i < d) will be fixed with a normal random generator. In the following consolidation phase, just the c_i shortest connections of each node will be preserved while the other (b-c_i) connections will be eliminated. Due to the random sequence the nodes have been distributed in the beginning, long distance connections will be preserved where short distance connections nevertheless will be favored.

A lot of algorithms to generate networks already exist, like for Small-World Networks presented by Kleinberg as well as research is done (like Adamic). Since the PLNGen algorithm does not try to create real Small-World Networks, it can meet a lower complexity of O(n) then more strict attemps. A lot of references about the subject of network theory are collected by Cosma Shalizi.

(Interactive demo of the PLNGen algorithm)

input regionSize        // The dimensions of the region, in which the network resides
input nodeCount         // The number of nodes in the network
input minimalConnNumber // Minimal connections of each node
input standardDeviation // Standard deviation to estimate node connectivity
input backConnDistance  // The backward connection distance

output nodes            // Container for the PLN
	
for (i = 0; i < nodeCount; i++)
    //Place the node in the region
    nodes[i].coordinates = random_uniform_point(regionSize)
    
    // Create basic connections
    for (k = 0; i > 0 && k < min(backConnDistance,i); k++)
        j = i-k-1 // Select partner
		
        // Calculate distance
        distance = get_distance(nodes[i].coordinates,nodes[j].coordinates)
		
        // Store connections
        nodes[i].connections[j] = distance
        nodes[j].connections[i] = distance
    
    // Define connectivity (randomly min+lambda)
    nodes[i].connectivity = minimalConnNumber+abs(random_normal(0,standardDeviation))
	
// Consolidate connections
foreach i in random_permute(0..nodeCount-1)	
    partners = sort_by_distance(index(nodes[i].connections))
	
    // Delete the longest connections
    for (k = partners.size-1; k > 0 && nodes[i].connections.size > nodes[i].connectivity; k--)
        j = partners[k]
        if nodes[j].connections.size > nodes[j].connectivity // if partner is not already to less connected
            delete(nodes[i].connections[j])
            delete(nodes[j].connections[i])