Semi-Supervised Learning in Complex Networks - Silva, Thiago C.; Zhao, Liang (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC); 2011: Anais do VIII Encontro Nacional de Inteligência Artificial, 2011)
Semi-Supervised Learning (SSL) is a machine learning scheme which is able to employ both labeled and unlabeled samples in the training process. In this paper, we propose a semi-supervised classification model based on a combined random-deterministic walk of particles in the network (graph) constructed from the input data set. The particles of the same class cooperate among them, while the particles of different classes compete with each other to propagate class labels to the whole network. A rigorous definition of the model is provided. An interesting feature of the proposed model is that each particle only visits a portion of nodes potentially belonging to it due to the competition mechanism. Thus, many long range, apparently meaningless visits are avoided. As a result, the proposed model can achieve a good classification rate while exhibiting low computational complexity order in comparison to other network-based semi-supervised algorithms. Computer simulations carried out for synthetic and real-world data sets show good performance of the model.