Node classification in uncertain graphs

In many real applications that use and analyze networked data, the links in the network graph may be erroneous, or de-rived from probabilistic techniques. In such cases, the node classification problem can be challenging, since the unrelia-bility of the links may affect the final results of the classi-fication process. If the information about link reliability is not used explicitly, the classification accuracy in the under-lying network may be affected adversely. In this paper, we focus on situations that require the analysis of the uncer-tainty that is present in the graph structure. We study the novel problem of node classification in uncertain graphs, by treating uncertainty as a first-class citizen. We propose two techniques based on a Bayes model and automatic parameter selection, and show that the incorporation of uncertainty in the classification process as a first-class citizen is beneficial. We experimentally evaluate the proposed approach using different real data sets, and study the behavior of the algo-rithms under different conditions. The results demonstrate the effectiveness and efficiency of our approach