Estudio comparativo entre el algoritmo de Kleinberg y el algoritmo Biased Selection para la construcción de redes small world



Título del documento: Estudio comparativo entre el algoritmo de Kleinberg y el algoritmo Biased Selection para la construcción de redes small world
Revista: Computación y sistemas
Base de datos: PERIÓDICA
Número de sistema: 000423229
ISSN: 1405-5546
Autores: 1
Instituciones: 1Universidad Politécnica Salesiana, Grupo de Investigación en Inteligencia Artificial y Tecnología de Asistencia, Cuenca, Azuay. Ecuador
Año:
Periodo: Abr-Jun
Volumen: 21
Número: 2
País: México
Idioma: Español
Tipo de documento: Artículo
Enfoque: Experimental, aplicado
Resumen en español Actualmente las redes de tipo small world constituyen un tema muy importante en nuestro entorno, pues están presentes en varios fenómenos naturales y artificiales. Un objetivo de muchos algoritmos desarrollados para tratamiento de grafos es conseguir que un nodo cualquiera logre establecer una conexión directa con otro nodo del grafo seleccionado al azar obteniendo un “vecino lejano”. Este trabajo muestra un estudio comparativo entre dos algoritmos que logran este objetivo: Kleinberg y Biased Selection. Se demuestra por medio de experimentos que los dos algoritmos son capaces de obtener la distribución de Kleinberg. Se concluye que el algoritmo de Kleinberg obtiene una distribución de muestreo que es directamente proporcional a la distancia Euclidiana, y Biased Selection, a pesar de que también obtiene una distribución directamente proporcional a la distancia Euclidiana, permite que un nodo lejano pueda ser determinado como vecino lejano con mayor frecuencia
Resumen en inglés Actually Small-World Networks is a very important topic, it is present in a lot of applications in our environment. A target of many algorithms is to establish methods to get that any node in a graph can establish a direct connection with a randomly “long-range neighbor”. This work is comparative study between two algorithms that get this target (Kleinberg and Biased Selection), I demonstrate by my experiments that both get the Kleinberg’s distribution. I conclude that the Kleinberg’s algorithm distribution maintains a probability directly proportional to Euclidian distance, and Biased Selection, although also maintains a probability directly proportional to Euclidian distance, allows that a node can get a farther node as “long-range neighbor” more frequently
Disciplinas: Ciencias de la computación
Palabras clave: Redes,
Algoritmos,
Selección sesgada,
Cadenas de Markov,
Grafos,
Paseos aleatorios,
Small world
Keyword: Networks,
Algorithms,
Biased selection,
Graphs,
Markov chains,
Random walks
Texto completo: Texto completo (Ver HTML) Texto completo (Ver PDF)