Development of advanced data mining algorithms for the analysis of directed networks

There are many systems which can be represented as a network, where the parts of the system are nodes and the connections between the parts are the edges. Researchers proposed numerous different network types such as internet networks, citation networks, and transportation networks. Also, numerous analysis tools have been introduced to investigate the structures and pattern of connections of networks. However, existing research is mostly focused on undirected and static networks and analysis of directed dynamic networks, especially citation networks, has received little attention from the researchers. In this dissertation, we present new methodologies for the analysis of directed networks. We first propose an anomaly (outlier) detection technique based on nonnegative matrix factorization for directed patent citation network (PCN). We have developed a clustering method based on NMF, and an anomaly score function that exploits the clustering result. The proposed outlier ranking method leverages the patent-level analysis as well as group-level analysis in order to measure the graph-based outlierness of a patent. We validate our proposed anomaly ranking methods using small artificial datasets. We then conduct experiments using real-world patent citation network. Results reveal that the proposed outlier ranking and detection method outperforms existing approaches. Secondly, we present a regularized asymmetric nonnegative matrix factorization (RANMF) algorithm for clustering in directed networks. The proposed algorithm assumes that if two nodes are similar to each other in the original basis, their representatives in new basis should be close to each other. Therefore, similar nodes appear in the same cluster. The proposed algorithm is for clustering nodes in a given directed network under the guidance of prior similarity information of the network and SVD-based initialization. We also provide proof of the convergence of RANMF algorithm and real-world experiments to show its performance. The experiments reveal that RANMF algorithm is a better solution for clustering in directed networks compared to other clustering algorithms. Finally, we develop a time-aware ranking method for the identification of important and influential patents in dynamic patent citation network. While the existing ranking methods fail to distinguish the citing and cited patent for the importance of cited patent, the proposed ranking method successfully distinguish them by exploiting the time information of not only citing patent but also the time information of cited patent. We present the performance of our method on real-world patent citation data and compare it to other ranking metrics. The results reveal that our proposed method not only successfully rank the patents in importance but also successfully identifies the influential patents in a dynamic patent citation network.Ph.D.Includes bibliographical reference