Analíticas de redes y grafos

Abstract

La teoría de grafos puede ser una herramienta muy útil para analizar y optimizar los sistemas de transporte, la arquitectura urbana y muchos otros aspectos de la planificación urbana, así como conocer las personas más influyentes en una red social o incluso en una red de empresas o trabajadores según sus conexiones. Por ejemplo, se pueden usar grafos para representar la red de carreteras de una ciudad, donde los nodos serían los cruces y las aristas serían las calles que las conectan y así poder analizar la distribución de las calles y la organización de ella gracias a los diferentes algoritmos de grafos. El objetivo de este trabajo es el análisis de la estructura y conexiones de las calles de Sevilla a través de aplicaciones de metodologías de grafos para la propuesta de diferentes soluciones a partir de los datos obtenidos, en función del conexionado de sus carreteras y las relaciones que puedan haber entre ellas, y el análisis y demostración del funcionamiento del algoritmo de PageRank en una red de seguimiento entre un grupo de personas en función de sus conexiones entre ellos y la importancia que ha tenido en el buscador más importante hoy en día que es Google. Para ello, y gracias a la librería NetworkX y OSMnX y siendo programado en Google Collab, se utilizarán las técnicas de análisis PageRank, Betweenness Centrality y detección de comunidades de Louvain, implementadas mediante el lenguaje de programación Python. En primer lugar, se recopilarán los datos de la ciudad de Sevilla, es decir, la interconexión de sus carreteras y se graficarán para ver su conexionado, y a continuación, se aplicarán los diferentes algoritmos de Betweenness Centrality y el de detección de comunidades de Louvain y su posterior grafo para ver cómo han analizado estos algoritmos la ciudad de Sevilla. También, se desarrollará otro ejemplo en el que se aplicará el algoritmo de PageRank y se demostrará el funcionamiento de éste en cuanto a las relaciones y conexiones de diferentes personas en una red social y cómo puede variar tanto las puntuaciones y la influencia de las personas en cuanto a sus seguidores. Cómo resultado de estos algoritmos, comprenderemos mejor las interacciones y las relaciones de los grafos y redes, pues tienen implicaciones muy significativas en campos como el análisis de organización en una ciudad, gestión del tráfico o interacciones e influencia en redes sociales.

Graph theory can be a very useful tool to analyse and optimise transport systems, urban architecture, and many other aspects of urban planning, as well as to know the most influential people in a social network or even in a network of companies or workers according to their connections. For example, graphs can be used to represent the road network of a city, where the nodes would be the crossroads and the edges would be the streets that connect them and thus be able to analyse the distribution of the streets and the organisation of it thanks to the different graph algorithms. The aim of this work is the analysis of the structure and connections of the streets of Seville through applications of graph methodologies for the proposal of different solutions from the data obtained, depending on the connection of its roads and the relationships that may exist between them, and the analysis and demonstration of the operation of the PageRank algorithm in a tracking network between a group of people according to their connections between them and the importance it has had in the most important search engine today which is Google. For this purpose, and thanks to the NetworkX and OSMnX libraries and being programmed in Google Collab, the PageRank, Betweenness Centrality and Louvain's community detection analysis techniques will be used, implemented using the Python programming language. First of all, the data of the city of Seville will be collected, i.e., the interconnection of its roads and plotted to see how they are connected, and then the different algorithms of Betweenness Centrality and Louvain's community detection algorithm and its subsequent graph will be applied to see how these algorithms have analyzed the city of Seville. Also, another example will be developed in which the PageRank algorithm will be applied, and it will be demonstrated how it works in terms of the relationships and connections of different people in a social network and how it can vary both the scores and the influence of people in terms of their followers. As a result of these algorithms, we will better understand the interactions and relationships of graphs and networks, as they have very significant implications in fields such as organisational analysis in a city, traffic management or interactions and influence in social networks.