Revista: | Computación y sistemas |
Base de datos: | PERIÓDICA |
Número de sistema: | 000423229 |
ISSN: | 1405-5546 |
Autores: | Arcos Argudo, Miguel1 |
Instituciones: | 1Universidad Politécnica Salesiana, Grupo de Investigación en Inteligencia Artificial y Tecnología de Asistencia, Cuenca, Azuay. Ecuador |
Año: | 2017 |
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) |