An algorithm for identifying the best current friend in a social network

Un algoritmo para determinar el mejor amigo actual en una red social

A research field in the area of social networks (SNs) is the identification of some types of users and groups. To facilitate this process, a SN is usually represented by a graph. The centrality measures, which identify the most important vertices in a graph according to some criterion, are usual tools to analyze a graph. One of these measures is the PageRank (a measure originally designed to classify web pages). Informally, in the context of a SN, the PageRank of a user i represents the probability that another user of the SN is seeing the page of i after a considerable time of navigation in the SN. In this paper, we define a new type of user in a SN: the best current friend. The idea is to identify, among the friends of a user i, who is the friend k that would generate the highest decrease in the PageRank of i if k stops being his/her friend. This may be useful to identify the users/customers whose friendship/relationship should be a priority to keep. We provide formal definitions, algorithms and some experiments for this subject. Our experiments showed that the best current friend of a user is not necessarily the one who has the highest PageRank in the SN nor the one who has more friends.

Un campo de investigación en el área de las redes sociales (RSs) es la identificación de ciertos tipos de usuarios y de grupos. Para facilitar este proceso, una RS se suele representar mediante un grafo. Las medidas de centralidad, las cuales identifican los nodos más importantes en un grafo según algún criterio, suelen ser usadas para analizar un grafo. Una de estas medidas es el PageRank (una medida inicialmente concebida para clasificar las páginas web). Informalmente, en el contexto de las RSs, el PageRank de un usuario i representa la probabilidad de que otro usuario de la RS esté viendo la página de i luego de un tiempo considerable de navegación por la RS. En este artículo, se define un tipo de usuario en una RS: el mejor amigo actual. La idea es identificar, entre los amigos de i, quién es el amigo k que generaría el mayor decremento en el PageRank de i, si k dejara de ser amigo de i. Esto puede ser útil para identificar los usuarios/clientes cuya amistad/relación es prioritario conservar. En este artículo se presentan las definiciones formales,  algoritmos y  experimentos al respecto. Los experimentos demostraron que el mejor amigo actual de un usuario no es necesariamente aquel que tiene el mayor PageRank en la RS ni aquel que tiene más amigos.