| As a hot research topic in data mining,machine learning algorithms are good at handling structured data with vectors.However,due to policies,regulations and protection of user privacy,sometimes we cannot get complete and useful features for each node which limits the application of machine learning algorithms.Most complex systems in nature can be represented by networks.Therefore,network analysis,which is also known as a hot research topic of data mining,is not limited by the data set.We usually take the adjacency matrix or adjacency list to represent network.But networks in the real-world suffer from data sparsity.With the continuous expansion of network scale,representing network with adjacency matrix requires a huge amount of memory,sometimes even impossible,in which a lot of useless information is stored.In addition,computers are not good at processing the adjacency list.What is more important,most network analysis algorithms work in batch mode,which makes it difficult to respond a personal request in time.Therefore,network embedding develops gradually and has aroused considerable research interest in network analysis.Network embedding aims to learn the latent,low-dimensional representations of vertexes in a network,while preserving network topology structure and inherent properties.In this way,each vertex can be represented by a short,compact vector.When we want to study the whole network or part of the nodes,we only need to use vector-based machine learning methods to perform network analysis tasks.Network embedding provides a easier way to analyze the network.A number of works,such as Deep Walk,Node2 vec and LINE,have been proposed by applying advances in machine learning.Network embedding has been successfully applied in many areas.Despite its great potential,there are still several key challenges in the promotion of network embedding.For example,the conventional community detection algorithm cannot be applied in the new vector space.Many studies have used k-means to cluster the vertexes instead.We visually study the real-world networks in the new vector space,and find that the communities are always lying around several manifolds.In the low dimensional manifold structure data space,the communities can be arbitrary shapes.Thus,a clustering algorithm,without requiring too many parameters,that can identify arbitrary shaped clusters and estimate the number of clusters is needed.The contributions of this paper are summarized as follows:1.We study the first-order proximity,the second-order proximity and Skip Gram model and prove that we can both preserve the first-order proximity and the second-order proximity by maximizing the Skip Gram model.Inspired by the theoretical analysis mentioned above,we propose a method named Preserving Proximities for Network Embedding(PPNE).We apply PPNE to link prediction,and the experimental results show that our algorithm can improve the prediction accuracy while maintaining low time complexity.2.We analyze the properties of Minimax distance and explain the relationship between Minimax distance and minimum spanning tree.After that,we propose a global optimal path-based clustering algorithm(GOP).GOP needs only one parameter,i.e.,the number of clusters which can be estimated by the decision graph.Experimental results on synthetic data sets and real-world data sets demonstrate that GOP can recognize all kinds of clusters regardless of their shapes.The advantages mentioned above make GOP a good candidate as a general clustering algorithm.3.We propose a community detection algorithm by combining the two algorithms mentioned above,and compare it with the state-of-the-art community detection algorithms on some real-world data sets.Experimental results show that our algorithm can be successfully applied in this domain and replace the conventional community detection algorithms. |
