Abstract
In this paper, we consider a natural ranking problem that arises in settings in which a community of people (or agents) are engaged in regular interactions with an end goal of creating value. Examples of such scenarios are academic collaboration networks, creative collaborations, and interactions between agents of a service delivery organization. For instance, consider a service delivery organization which essentially resolves a sequence of service requests from its customers by deploying its agents to resolve the requests. Typically, resolving a request requires interaction between multiple agents and results in an outcome (or value). The outcome could be success or failure of problem resolution or an index of customer satisfaction. For this scenario, the ranking of the agents of the network should take into account two aspects: importance of the agents in the network structure that arises as a result of interactions and the value generated by the interactions involving the respective agents. Such a ranking can be used for several purposes such as identifying influential agents of the interaction network, effective and efficient spreading of messages in the network. In this paper, we formally model the above ranking problem and develop a novel algorithm for computing the ranking. The key aspect of our approach is creating special nodes in the interaction network corresponding to the outcomes and endowing them independent, external status. The algorithm then iteratively spreads the external status of the outcomes to the agents based on their interactions and the outcome of those interactions. This results in an eigenvector like formulation, which results in a method requiring computing the inverse of a matrix rather than the eigenvector. We present several theoretical characterizations of our algorithmic approach. We present experimental results on the public domain real-life datasets from the Internet Movie Database and a dataset constructed by retrieving impact and citation ratings for papers listed in the DBLP database. © 2012 Springer-Verlag London.