Paper Info
Title
Structural Neighborhood based Classification of Nodes in a Network
Abstract
Classification of entities based on the underlying network structure is an important problem. Networks encountered in practice are sparse and have many missing and noisy links. Statistical learning techniques have been used in intra-network classification; however, they typically exploit only the local neighborhood, so may not perform well. In this paper, we propose a novel structural neighborhood-based classifier learning using a random walk. For classifying a node, we take a random walk from the node and make a decision based on how nodes in the respective k^th-level neighborhood are labeled. We observe that random walks of short length are helpful in classification. Emphasizing role of longer random walks may cause the underlying Markov chain to converge to a stationary distribution. Considering this, we take a lazy random walk based approach with variable termination probability for each node, based on the node's structural properties including its degree. Our experimental study on real world datasets demonstrates the superiority of the proposed approach over the existing state-of-the-art approaches.
Year
DOI
Venue
2016
10.1145/2939672.2939782
KDD
Keywords
Field
DocType
Graph-based semi-supervised learning,Relational learning,Collective classification
Data mining,Computer science,Statistical relational learning,Random walk,Markov chain,Exploit,Stationary distribution,Artificial intelligence,Classifier (linguistics),Machine learning,Decision-making,Network structure
Conference
Citations 
PageRank 
References 
7
0.44
10
Authors
2
Name
Order
Citations
PageRank
Sharad Nandanwar1112.16
M. Narasimha Murty282486.07