Core Network Based Multi-label Classification in Large-Scale Social Network Environments

Multi-label classification in social network environments is becoming a key area of data mining research in recent years. Given some nodes´ labels (i.e., the sources), the task is to infer some other nodes´ labels (i.e., the targets) in the same network. Relational classification methods, which leverage the correlation of labels between linked instances, have been shown to outperform traditional classifiers. However, typical relational classification methods make predictions about targets by executing collective inference over the full set of unlabeled nodes, and then to get the labels of targets. In large-scale social network environments, when we want to predict only a specific node´s labels, collective inference procedure can seriously limit the efficiency of relational classifiers and make it inapplicable to large-scale social networks. In this paper, we first propose a new concept Core Network which is composed of the shortest paths that link sources and targets. These paths have the most significant influence on classification. Then we propose a novel Heuristic Core Network discovery (i.e., HCN) algorithm to discover the core network. Finally, we propose two classification algorithms HCN-wvRN and HCN-SCRN. Both algorithms are capable of handling large-scale social networks in an efficient way. The difference between two algorithms is HCN-wvRN consumes much less time than existing methods, while HCN-SCRN can achieve higher classification accuracy than HCN-wvRN. We test on several real-world datasets, the experimental results demonstrate that our proposed methods make great improvements in algorithm efficiency while maintaining the classification accuracy.