Node Influence Model In Complex Network And Its Applications

Many systems in real world can be described by complex networks, such as the World Wide Web, Internet, social network, terrorist criminal networks, paper cooperation networks, protein interaction networks, financial networks, transportation networks, power networks. Quantitative analysis of the degree of importance of all nodes in complex networks, so that mining the core nodes, is one of the important issues in the study of complex networks.The widely uesd node importance evaluation methods are degree, betweenness, closenesss, PageRank and K-shell. Node degree only consider the local information. K-shell divides the nodes into different layers but not precise enough. PageRank is only effective in directed network. Both the betweenness and closeness depend on the shortest paths, but can not dig out the important nodes in many cases. Node influence model proposed in this paper, can dig out the core node more effectively. Based on node influence, we propose community detection algorithm, cancer classification algorithm and cluster algorithm. The main contributions of this thesis are summarized as follows:(1) We propose the node influence model. We first propose a node on a single node k influence, k is the length of the path. And we have given a proof that the influence will be convergence when k tends to be infinity. In the proof, we also found that in the fully connected two bipartite network, a node to other nodes of the k effect when k tends to infinity would converge to the same value. Through the experiments on the Zachary network, Yeast network, USAIR network and Flickr image tag network, we can see the node influence is more effective.(2) We propose community detection based on node influence. First, we calculate each node’s influence and mining the community core nodes. Then we calculate the influence from these core nodes to every node in the network of L length and draw the final result. Through the experiments in Zachary network, American football network, Dolphin club network, Polbooks network, we can see that our community detection algorithm is more effective. Comparing to GN algorithm, Newman algorithm and Louvain algorithm, the communities found by our community detection algorithm based on node influence are more similar to the true communities.(3) We propose cancer classification algorithm based on node influence. Compared with the traditional classification, cancer gene expression data has the characteristics, such as high dimension, small sample size and uneven distribution. In the cancer classification algorithm based on node influence, we first bulid a similar network of sample data. Then calculate each training sample node influence and obtain the similarity of each test sample and each class. Finally, every test sample is assigned to the class with highest similarity. Experimensts through breast cancer, central nervous system tumor, colon cancer, prostate cancer, lung cancer, acute lymphoblastic leukemia, we can see that our classification algorithm is more effective. Comparing to support vector machine, K-nearest neighbor, decision tree, CART tree, naive Bayes classification, and our cancer classification algorthm obtains highest classification accuracy.(4) We propose clustering algorithm based on node influence. The algorithm first constructs a similarity matrix between the data points, and this is the adjacency matrix of a network. Then we calculate the influence of each node and dig out the each cluster core node. At last, every node is assigned to the cluster with highest similarity between every node and cluster core node. Compared with the existing clustering methods, our clustering algorithm do not need to specify the number of clusters, just need a rough prediction of maximum number of clusters. Through the experiments on the Spiral, Aggregation, Flame, Compound, R15, Iris, Wine and soybean, we can see that the clustering algorithm based on node influence is more effective. Comparing to K-means, K-medoids, hierarchical clustering, Gauss mixture model and spectral clustering, clusters found by our clustering algorithm are more similar to the true clusters.