Ranking large networks : leadership, optimization and distrust

Large networks mathematically models the connections between items (generally millions or billions of items). For instance, people using their mobile phones live in a network where they are connected by their calls, SMSs, MMSs, etc. Another example is given by the set of webpages in the World Wide Web that are connected by their hyperlinks. The representation of these large databases by networks allows us to extract different type of hidden information as the sets of communities and the importance of the nodes in the network. We investigate the second issue where the target is to assign a rank to all nodes that will be relevant for classifying them by order of importance in some context. We will consider five topics related to ranking methods for networks: (1) Ranking can be used to identify the leaders among the customers of a mobile phone company, that is, people who has the capacity to influence their contacts. Surprisingly enough, the study shows that some measure based on the structural position of a customer in the mobile phone network provides relevant information to identify leaders. (2) We call a degree leader someone who has more friends than his friends. We could expect that when your number of friends increases, the probability to be degree leader becomes higher. That question is analyzed for random networks that have the same degree distribution than real social networks. (3) We consider the problem of maximizing the average PageRank of a set of webpages when we consider two realistic constraints: one can only control the hyperlinks of one's webpages and one must points to the rest of the web. (4) The PageRank (and many other ranking methods) is based on a random walk over the network. We extend the random walk to the case where connections of distrust are present in the network. (5) Opinions can be modeled by a network where the connections are directed and weighted by a vote. We propose an iterative filtering that alternatively uses the credibility of the votes to determine the reputations of the nodes, and then the reputation of the nodes to update the real bias of the votes.(FSA 3) -- UCL, 200