Network discovery using content and homophily

Abstract

A new approach for targeted graph sampling is proposed in which graph sampling and classification occur together, and content-based homophily is exploited to achieve improved classification performance. The application of network discovery of relevant content is considered using an approach that may be generalized to a broad class of vertex properties. The resulting procedure provides the initial step of a graph analytic processing chain whose performance is directly affected by the quality of graph sampling. The performance of the algorithm is measured with real network data and content observed on a social media site. Precision-Recall performance improvements of 30% are demonstrated with this dataset, compared to a baseline approach that does not exploit homophily. Because real-world graphs grow exponentially, this performance improvement may have a significant impact on graph analytic algorithms with sensitivities to the graph sampling quality.