So any node update order can be applicable to the label propagation process. Therefore, for the unweighted network, formula (5) can be simplified as lunew=maxl∑i∈Nuδli,l. (6) At this point, NILP algorithm becomes the original label propagation algorithm LPA. Hence, we can draw the conclusion that LPA is merely a simple case of our α-degree neighbors label propagation algorithm NILP. 3.3. Complexity selleckchem Analysis In this subsection, we analyze and compare
both time and space complexity of various label propagation based algorithms α-NILP, LPA, LPAm, and LHLC. The pertinent data is shown in Table 1. In terms of time complexity, our algorithm α-NILP consists of three parts which are the calculation
of α-degree neighborhood impact, the node sorting process, and the label propagation process. In the calculation of impact values, our algorithm needs to traverse all the nodes in the network and the 1-degree neighbors of all the nodes, so the time complexity is O(αm + n), where m and n are, respectively, the number of edges and nodes in the network. In the sorting process, we adopt quick sort algorithm and the time complexity is O(nlog n). The time complexity of the label propagation process is O(nlog n). Therefore, the overall time complexity is O(nlog n) when O(m) = O(n) in a sparse scale-free network. Table 1 The comparison of time and space complexity of four algorithms LPA, LPAm, LHLC, and α-NILP based on label propagation (n is the number of nodes in the network). Then, we analyze the space complexity of our α-NILP algorithm. Because the algorithm creates n nodes and n initial communities, we use adjacency lists to describe the 1-degree relationship between nodes and the correspondence
between nodes and communities, which occupies O(2m + n) and O(n + n) space, respectively, and amounts to the total space complexity of O(n). In summary, in the case of the same time complexity, LPA, LHLC, and α-NILP have lower space complexity. This is because these algorithms run without using adjacency matrix, which leads to the decline of the volume of data involved in the creating, reading, and manipulating Batimastat process. The running time elapsed also dwindles due to the reduction in the space complexity, implying that the above three algorithms also run faster. 4. Experimental Results and Analysis In this section, we evaluate the performance of the proposed algorithm α-NILP through experiments. Our algorithm is implemented using ANSI C++. All the experiments were conducted on a PC with 3.20GHz processors and 4.0GB memory. 4.1. Data Sets To evaluate the performance of our algorithm, we use the following three real-world networks. Zachary’s Karate Club Network. A network of social relations between members of an American university karate club (http://networkdata.ics.uci.edu/data.