A Method For Node Similarity In Dynamic Clustering

With the rapid development and continuous improvement of complex networks, the dynamic clustering analysis become an important research direction of that because of its extensive application. Facet Net method becomes a very popular kind of algorithm in many dynamic clustering algorithms due to its relatively superior performance. The work of this paper is conducted on it. Facet Net algorithm ueses boolean discrete value to measure similarity between two nodes and clustering nodes with matrix decomposition. But this node similarity measure has the following three defects: First, the relationship between nodes have the same weight and can't distinguish their importance.Second, when the network has disturbance, that measure can't eliminate interference and accurately depict the relationship between nodes. Last, that mearsure doesn't take into account the impact of changing edges between adjacent networks.Based on the above three points, our paper improve the node similarity of Facet Net algorithm.First, Jaccard coefficient is used to measure the connection strength between nodes by switching the boolean discrete value to a continuous one. The method not only compute the importance of edges, but also eliminate interference which measure the connection of nodes accurately. Second, inspired by sequential overhead technology in evolutionary clustering framework, we establish linear equation through the change rate of edge and regard it as factor to banlance historic information and the current topological characteristics of network to reconstruct nodes similatiry. It solves the problem brought by the network scheduling and to some extent, improvs the algorithm performance. Finally do clustering on the basis of those results.Our method is verified by artificial and real networks including dynamic networks of three different structure and football club network and evaluated by four clustering index of precision, recall, normalized mutual information and modularity function. Experimental results show that the more complex network structure is, the more outstanding performance of algorithm is. That performance on four indicators. Precision is improved by an average of 11%. Rrecall is improved by an average of 14.3%. The NMI is improved by an average of 14%. And Modularity is improved by an average of 4%. In real networks, modularities of all time are higher which indicates the good inheritance to the structure of “dense inside and loosing outside”. In addition, through the analysis and comparison of the clustering results from adjacent time, the improved algorithm can determine the node's ownership more accurately, correct some false results and find some communities whose structure are hidden and small. It can also find more appropriate communities for isolated nodes according to historical information.In conclusion, the method has improved on precision, recall and modularity. It can identify communities comprehensively and accurately. This method is suitable for more complex structure of network, especially more edges appear between different communities. That is effective to enhance and complement Facet Net algorithm.