Exponentially Twisted Sampling for Centrality Analysis and Community Detection in Attributed Networks

摘要

In this paper, we conduct centrality analysis and community detection for attributed networks. An attributed network, as a generalization of a graph, has node attributes and edge attributes that represent the "features" of nodes and edges. Traditionally, centrality analysis and community detection of a graph are done by providing a sampling method, such as a random walk, for the graph. To take node attributes and edge attributes into account, the sampling method in an attributed network needs to be twisted from the original sampling method in the underlining graph. For this, we consider the family of exponentially twisted sampling methods and propose using path measures to specify how the sampling method should be twisted. For signed networks, we define the influence centralities by using a path measure from opinions dynamics and the trust centralities by using a path measure from a chain of trust. For attributed networks with node attributes, we also define advertisement-specific influence centralities by using a specific path measure that models influence cascades in such networks. For networks with a distance measure, we define the path measure as the total distance along a path. By specifying the desired average distance between two randomly sampled nodes, we are able to detect communities with various resolution parameters. Various experiments are conducted to further illustrate these exponentially twisted sampling methods by using three real datasets: the political blogs, the MemeTracker dataset, and the WonderNetwork.