Prominence Ranking in Graphs with Community Structure

Abstract

We consider prominence ranking in graphs involving actors, their artifacts and the artifact groups. When multiple actors contributing to an artifact constitutes a social tie, associations between the artifacts can be used to infer prominence among actors. This is because prominent actors will tend to collaborate on prominent artifacts, and prominent artifacts will be associated with other prominent artifacts. Our testbed example is the DBLP co-authorship graph: multiple authors (the actors) collaborate to publish research papers (the artifacts); collaboration is the social tie. Papers have prominence themselves (eg. quality and impact of the work) and the prominence of the venues are tied to the prominence of the papers in them. We use our methods to infer prominence based on the venue-based associations of papers, and compare our rankings with external citation based measures of prominence. We compare with numerous other ranking algorithms, and show that the ranking performance gain from using the venues is statistically significant. What if there are no natural artifact groups like venues? We develop a new algorithm which uses discovered artifact groups. Our approach consists of two steps. First, we find artifact groups by linking artifacts with common contributors. Note that instead of finding communities of actors, we consider communities of artifacts. We then use these grouped artifacts in the prominence ranking algorithm. We consider different methods for obtaining the artifact groups, in particular a very efficient embedding based algorithm for graph clustering and show the effectiveness of our method in improving the ranking of actors. The inferred groups are as good as or better than the natural conference venues for DBLP.