1.Explica
A qué se refiere el grado de un vértice, diferencia también grado entrante y
Saliente

Para el caso de grafos no orientados,
El grado de un vértice es
Simplemente la suma de los pesos asociados a las aristas incidentes a este
Vértice. En caso de grafos no ponderados,
Cada enlace se encuentra ponderado por la unidad. Se considera la
Carácterística de grado positivo (entrante, indegree)
O negativo (saliente, outdegree)
De un vértice, como la suma de los pesos
Asociados a los arcos que llegan o sale de él respectivamente. (Hay ejemplo).

2.Explica en qué consisten las redes de
Coocurrencias de palabras

Es un
Tipo de red que se da habitualmente en Información y Documentación, cuyos
Enlaces se establecen mediante relaciones de segundo orden, basadas en la
Coocurrencia de palabras, esto es, cuando dos términos coocurren en un mismo
Documento. Para representar con detalle, se utilizan redes o grafos ponderados,
Donde los pesos de los enlaces normalmente significan similitud o cercanía. Dos
Términos muy frecuentes es muy probable que coocurran aunque sean palabras
Vacías, etc. Para ello normalmente se divide el número de coocurrencias por
Alguna medida del tamaño. Estudios recientes demuestran que la mejor forma de
Normalizar dichos valores es dividiendo por el tamaño de los dos nodos. Es
Decir, en el caso de los términos, por la frecuencia de cada término, o por la
Suma de coocurrencias que cada término tiene con otros términos. Además en este
último caso, si se multiplica el resultado por la suma total de coocurrencias
Entre términos, tiene el significado de ser mayor que uno cuando los términos
Coocurren con más probabilidad de la esperada, mientras que es menor que uno
Cuando coocurren con menos probabilidad de la esperada (dado el número de
Enlaces de cada término). Lógicamente esto se aplica a todas estas redes de
Segundo orden.

3.Explica las propiedades atribuidas a las redes
Libres de escala

 La
Alta frecuencia con la que aparecen vértices con un grado muy superior a la
Media. A estos vértices se les suelen llamar hubs

 Los hubs
principales, conectados entre sí y a otros vértices de grado alto con una
Cierta redundancia aleatoria, son seguidos de cerca por otros más pequeños,
éstos, a su vez, son seguidos por otros vértices con un menor grado aún, y así
Sucesivamente. Esta jerarquía permite una gran tolerancia a fallos.

 Por
Otro lado, si eliminamos unos pocos hubs elegidos específicamente, la
Red

simplemente
Se desmorona y se convierte en un conjunto de grafos aislados. Por lo que son vulnerables
Ante ataques intencionados.
Así, los hubs/conectores son a la vez la
Fuerza de las redes libres de escala y su talón de Aquiles.

 Se
Pueden descomponer en subredes conectadas (a través de los hubs) muy similares unas
A otras (motifs)
.

 La
Distancia media entre dos vértices de la red es muy pequeña en relación al
Tamaño de la misma. Está demostrado que una red libre de escala con el
Exponente entre 2 y 3 también tendrá un diámetro medio ultrapequeño

 Otra
Carácterística importante de las redes libres de escala es el coeficiente
De

agrupamiento, que
Disminuye a medida que aumenta grado nodal. Esta distribución también es power
Law. Esto significa que los vértices de grado bajo pertenecen a subredes
Muy densas que están conectadas entre sí a través de los hubs. El coeficiente
De clustering de la red disminuye al aumentar la misma, pero, no tanto como
En una red aleatoria.

4.Explica qué es el diámetro de la red y su relación
Con el efecto Small-World

El diámetro de una
Red es la geodésica más grande en la red. En otras palabras, es la distancia
Más grande entre todos los pares de nodos de la red.
El coeficiente de clustering en este tipo de redes, es mayor que el de
Los grafos aleatorios y permanece bastante estable al aumentar la red.

A
Partir de aquí hay un efecto small world (aumento del diámetro promedio
A menor ritmo que el logaritmo del número de vértices) y un modelo small
World (Watts-Strogatz). Éste es un modelo teórico en el que partiendo de
Una distribución espacial sistemática de los vértices y un conexionado en
Función de la distancia entre los mismos, el diámetro se logra disminuir mucho
Sustituyendo en algunos enlaces aleatorios los vértices origen y destino por
Otros aleatoriamente distantes. Este modelo se diseño pensando en la
Explicación del resultado del experimento de mundo pequeño y la teoría
De los seis grados.

5.Estructura de la web

En 1999 Broder y otros (de los centros de Altavista, IBM y Compaq) realizaron
Un análisis que reveló la siguiente interesante imagen de la estructura
Macroscópica de la web, aunque no se sabe si la estructura ha cambiado desde
Entonces, no hay estudios que confirmen lo contrario.
En esta macroestructura, la mayoría (más del 90%) de los aproximadamente 203
Millones de vértices forman una componente débilmente conexa.
Esta gran componente al utilizar la dirección de los enlaces, se divide:

SCC:

Una componente fuertemente conectada.

IN:

Consta de páginas desde las que puede llegar a la SCC, pero no a la
Inversa.

Posiblemente
Los nuevos sitios que la gente aún no ha descubierto

OUT:

Páginas que son accesibles desde la SCC, pero que no enlazan a ella, tales
Como empresas en las que los sitios web contienen sólo información interna.

TENDRILS:

Contienen páginas que no pueden llegar a la SCC, y a las que no se puede llegar
Desde la SCC.

Tal vez
El sorprendente hecho, es que el tamaño de la SCC era relativamente pequeño,
Unos 56 millones de páginas. Cada uno de los otros tres conjuntos conténía
Alrededor de 44 millones de páginas, por lo tanto, los cuatro conjuntos tienen
Aproximadamente el mismo tamaño.

Demostraron
También que el diámetro del núcleo central (SCC) era por lo menos 28, y que el diámetro
De la gráfica en su conjunto era superior a 500. Se demostró también que para
Un origen y un destino elegidos al azar, la probabilidad de que exista camino
Desde el origen al destino era sólo el 24%. También se mostró que, si existía
Un camino dirigido, su duración media era de unos 16. Del mismo modo, si
Existía un camino no dirigido, su duración media era de unos 6. Estos
Resultados han sido bastante estables en varios experimentos realizados.

6.Explica qué es el grado de centralización de la
Red

Es
También importante el grado máximo, importante para ver el grado de
Centralización de la red. A partir de las medidas de centralidad de los nodos
Se calculan medidas de centralidad de la red.
Una red será más
Centralizada, tendrá un mayor grado de centralización, cuando mayor diferencia
Haya entre los nodos más centrales y los más periféricos. En todos los casos
ésta se calcula como la variación de centralidad máxima entre los vértices de
La red dividido por la

variación
Máxima posible de una red de ese tamaño (normalmente una red en estrella). En
El caso de la cercanía surgen problemas si la red no es fuertemente conexa,
Puesto que aunque existe un procedimiento para calcular la cercanía utilizando
Solamente los nodos alcanzables,no sirve para calcular la cercanía de toda la
Red.

7.Explica qué es la modularidad

Un
Problema de este algoritmo es que continúa dividiendo hasta quedar aislados
Todos los vértices, de modo que no se sabe muy bien cuando parar. Con ese fin también
Proponen la modularidad como medida de la fortaleza de una determinada
Partición en comunidades. La base de dicha medida es la diferencia entre la
Proporción de enlaces que partiendo de un vértice de una comunidad tienen como
Destino otro vértice de la propia comunidad y la probabilidad de que un enlace
Tenga como origen y destino dicha comunidad. Calculando

dicha
Probabilidad como el producto de la proporción de enlaces que parten de una

comunidad
Y la de enlaces que llegan a esa comunidad. En el caso de redes no dirigidas
Dichas proporciones coinciden. Y en el caso de redes ponderadas, para el
Cálculo de la proporción se utiliza el peso de cada enlace:

8.Explica qué son los geodésicos y el grado de intermediación
Geodésico

Un geodésico
es el camino más corto entre dos vértices. La distancia de un
Vértice a otro es la longitud del geodésico que los une. Si los enlaces no
Están ponderados, normalmente se entiende por longitud de un camino el
Número de enlaces que tiene. Si están ponderados y el peso representa
Distancias, la longitud de un camino suele ser la suma de todos los
Pesos.

Aunque
A veces se utiliza otra métrica de Minkowski. Y si los pesos representan
Similitudes se puede utilizar el inverso de la similitud como distancia.

El grado
De intermediación geodésico o shortest path betweenness de un

vértice
O enlace es la proporción de todos los geodésicos de la red, que no comiencen o
Terminen en aquel vértice al que se le está calculando (en caso de que se esté
Calculando a un vértice), en que participa dicho vértice o enlace (es la medida
De intermediación más general).

9.Explica qué son las redes de cocitación

Es un
Tipo de red que se da habitualmente en Información y Documentación, cuyos enlaces
Se establecen mediante relaciones de segundo orden, y que se emplea , por
Ejemplo, cuando un documento cita otros dos, quedando patente la probabilidad
De que ambas fuentes citadas estén relacionadas por su contenido.

El
Esquema más básico es el siguiente; un documento A cita a otros documentos B y
C. Cuando esto sucede, existe la posibilidad de que B y C traten temas
Relacionados. La probabilidad aumenta o disminuye dependiendo de la distancia
Que haya entre las citas o referencias.

10.Explica en qué consiste un grafo y qué se
Diferencia de una red

Un grafo es un conjunto, no vacío, de
Objetos llamados vértices (o nodos) y una selección de pares de vértices,
Llamados enlaces que pueden ser orientados, arcos (arcs en inglés), o no,
Aristas (edges en inglés). Típicamente, un grafo se representa mediante una
Serie de puntos (los vértices) conectados por líneas (las aristas) o flechas
(los arcos).
Un grafo
Es una pareja de conjuntos G = (V, A), donde V es el conjunto de vértices, y A
Es el conjunto de enlaces, este último es un conjunto de pares de la forma
(u,v) tal que u,v є V y tal que u ≠ v .
El grafo puede ser no dirigido si los enlaces, aristas (edges)
No tienen sentido, es decir, (a,b) = (b,a). En los grafos dirigidos (o
dígrafos)
los arcos (arcs) tienen un sentido, es decir (a,b)
≠ (b,a), el primer vértice es el origen y el segundo el final. A veces
En un mismo grafo se representan aristas y arcos,
Normalmente en esos casos las aristas representan arcos en los
Dos sentidos. A veces a estos grafos se les llaman grafos mixtos.

La diferencia radica en que una red consiste en un grafo, más
Información adicional sobre los vértices y sobre las aristas o
Los arcos.

Muchas
Redes de uso cotidiano pueden ser modeladas con un grafo: una red de
Carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una
Ciudad.

11.Explica qué es la cercanía o closeness y como
Se calcula en las redes que no son fuertemente conexas

La cercanía
o closeness de un vértice es el número de vértices alcanzables desde
él dividido por la suma de las distancias a todos ellos. Algunas veces se
Define como el inverso de este valor. En el caso de que la red no sea fuertemente
Conexa surgen complicaciones, puesto que no todos los nodos son alcanzables
Desde cada nodo. En este caso se multiplica el valor obtenido por la fracción
De nodos alcanzables.

12.Explica la diferencia entre un semi-recorrido y
Un recorrido y entre un recorrido y un camino. Inventa un grafo con cuatro
Nodos y pon un ejemplo de cada.

Un semi-recorrido
(semiwalk)
de un vértice u a un vértice v es una secuencia de
Enlaces que unen una secuencia de vértices que comienza en u y termina
En v.

Un recorrido
(walk)
es un semi-recorrido con la condición adicional de que los enlaces
Deben tener el sentido del recorrido, es decir, uno comienza donde otro
Termina.

Un semi-camino
(semipath)
es un semi-recorrido donde ningún vértice se repite.

Un camino
(path)
es un recorrido en el que no se repite ningún vértice.

(dibujar
Ejemplos)

13.Explica qué es el grado de intermediación
Geodésico o shortest path betweenes

El grado
De intermediación geodésico o shortest path betweenness de un

vértice
O enlace es la proporción de todos los geodésicos de la red, que no comiencen o
Terminen en aquel vértice al que se le está calculando (en caso de que se esté
Calculando a un vértice), en que participa dicho vértice o enlace (es la medida
De intermediación más general).

En
Ocasiones, este valor se da también multiplicado por el número de pares de
Vértices, excluyendo a aquel vértice al que se le está calculando la
Betweenness (en caso de que se esté calculando a un vértice).

14.Explica que hace el algoritmo de pathfinder, su
Relación con la desigualdad triangular y la ventaja que han supuesto las pfnets
De cocitación.

El algoritmo Pathfinder fue desarrollado dentro de la ciencia cognitiva para
Determinar los enlaces más relevantes en una red. Los tipos de redes a los que
Da lugar (tras la poda que efectúa) se conocen como redes Pathfinder o PFNETs.

La poda
Que lleva a cabo este algoritmo se basa en eliminar aquellos enlaces que hacen
Que no se cumpla la desigualdad triangular.
Esta indica que la distancia
Directa entre dos puntos, será siempre menor o igual que la distancia entre los
Mismos pasando por un punto intermedio.
Una de las grandes ventajas de las PFNETs de cocitación es que ellas solas sin
Ayuda de otras metodologías son capaces de mostrar en gran medida lo que pasa
En un campo o una disciplina, a través de los enlaces entre los vértices que

se
Mantienen. Los autores dominantes y los enlaces que parten de ellos definen

especialidades,
Si un campo carece de grandes figuras, se ve inconexo, sin una estructura jerárquica.
Mientras que anteriormente, se necesitaban varias metodologías para extraer la
Mmisma información (correlación Pearson, MDS, PCA, Cluster Analisys, etc.),
Como ya se indicó en el tema 1.

15.Explica la diferencia entre una componente fuertemente
Conexa y una débilmente conexa

Un
Grafo fuertemente conexo es débilmente conexo. Por tanto, un subgrafo
Fuertemente conexo es débilmente conexo.

Sin
Embargo, una componente fuerte no tiene por qué ser componente débil. La
Diferencia está en que las componentes deben ser subgrafos máximos fuertemente
O débilmente conexo. Una componente fuerte será un subgrafo débilmente conexo,
Pero quizás no sea máximo.

·Ejemplo: En
La ciudad donde las plazas/intersecciones eran los nodos y las calles los
Enlaces. Podríamos tener una componente fuerte que estuviera formado por todos
Los nodos conectados en ambos sentidos, pero puede que hubiera algún nodo desde
El que se pudiera llegar, pero que, al estar conectado una calle de sentido
único (algo ilógico), no pudiera recibir vehículos.

En un
Grafo no dirigido, las componentes fuertes coinciden con las débiles.
Normalmente se puede considerar que las aristas tienen doble sentido, es decir
Como un arco en cada sentido.

Todos
Los nodos pertenecerán a una componente fuerte y a otra débil, que pueden
Coincidir o no. Un nodo aislado, pertenecerá por tanto a una componente fuerte
Formada por el mismo, y esta coincidirá con la componente débil a la que
Pertenece.

Un
Grafo por tanto, tendrá como máximo tantas componentes (fuertes o débiles) como
Nodos tenga.

16.Sobre la equivalencia estructural:

Dos
Vértices son estructuralmente equivalentes si tienen idénticos enlaces
Consigo mismo, el uno con el otro y con el resto de vértices, es decir, tienen
Idénticas filas y columnas en la matriz de adyacencia. La equivalencia
Estructural está basada en la similitud o diferencia entre vértices con
Respecto a sus filas y columnas en la matriz de adyacencia. La diferencia o
Distancia entre

los
Patrones de enlaces puede ser calculada y expresada por un índice, por ejemplo,
Entre 0 (completamente similares) y 1 (completamente diferentes) (por ejemplo
La proporción de enlaces diferentes (sin contar autoenlaces), aunque se pueden
Utilizar muchas otras medidas de similitud).

17.Explica en qué consisten las relaciones de
Segundo y tercer orden en Información y Documentación

Las
Relaciones que he llamado de primer orden son fáciles de establecer. Las
Relaciones de un autor con sus trabajos, un término con los documentos en los
Que aparece, o un trabajo con los trabajos que lo citan o que cita, por
Ejemplo.

Las de
Segundo orden, las he llamado así porque se basan en relaciones de primer
Orden. Por ejemplo un autor con sus coautores, un término con los términos que
Aparecen en los mismos documentos, o un trabajo con los trabajos que son
Cocitados (citados por los mismos documentos). Además estas relaciones admiten
Una cierta ponderación, por ejemplo el número de trabajo que coescriben, el
Número de documentos en los que dos palabras coinciden, o el número de veces
Que son cocitados. Y además estas relaciones no suelen ser dirigidas.

Bueno,
Pues las de tercer orden las he llamado así porque se basan en las de segundo
Orden, y también suelen ser ponderadas y no dirigidas. Pero, en lugar de
Basarse en lo más inmediato, van a tener una visión más global. Por ejemplo, en
Lugar de tener en cuenta sólo si dos autores coescriben muchos trabajos juntos,
Tienen en cuenta si coescriben trabajos con los mismos autores, en lugar de
Tener en cuenta si dos términos aparecen en los mismos documentos, van a
Valorar si coocurren con los mismos términos, o en lugar de tener en cuenta si
Dos trabajos son muy cocitados van a tener en cuenta si son cocitados con los
Mismos trabajos.

Y eso
Se consigue representando las relaciones de segundo orden de forma vectorial y
Aplicando una medida de similitud como el coseno (que se ve en PAI). Es decir,
En nuestros ejemplos, cada autor se representa con un vector con tantas
Componentes como autores hay, y donde cada componente indicará el número de
Coautorías que tiene con el autor correspondiente a la componente, cada término
Se representa por un vector con tantas componentes como términos tenemos y
Donde cada componente indicará el número de coocurrencias que tiene con el
Término correspondiente a la componente, y cada trabajo se representa por un
Vector con tantas componentes como trabajos tenemos y donde cada componente
Indicará el número de cocitas que tiene con el trabajo correspondiente a la
Componente.

18.Explica qué son las comunidades y el algoritmo
Que proponen Newman y Girvan para detectarlas

Algunos
Autores denominan comunidades en análisis de redes a las subredes densamente conectadas,
Un concepto similar pero menos estricto que grupo cohesivo.

Los
Enlaces entre comunidades distintas tendrán un alto grado de

intermediación/betweenness,
Ya que todos los caminos entre los vértices de las comunidades que enlazan
Tendrán que pasar por ahí. De modo que Newman y Girvan para descubrir la estructura
De comunidades proponen el siguiente algoritmo:

1.
Calcular el grado de intermediación/betweeness (el del caminante aleatorio o el

geodésico)
De todos los enlaces de la red.

2.
Eliminar aquel enlace de mayor grado de intermediación

3.
Volver al paso 1

Está
Demostrado que este algoritmo obtiene buenos resultados, y que no le afecta
Mucho ni la ponderación de los enlaces, ni la medida de intermediación
Utilizadas. De todos modos recordemos que de manera general, y en este caso en
Particular la partición de un grafo es un problema NP-completo, y por tanto no
Abordable para redes grandes.

Un
Problema de este algoritmo es que continúa dividiendo hasta quedar aislados
Todos los vértices, de modo que no se sabe muy bien cuando parar. Con ese fin
También proponen la modularidad como medida de la fortaleza de una
Determinada partición en comunidades. La base de dicha medida es la diferencia
Entre la proporción de enlaces que partiendo de un vértice de una comunidad
Tienen como destino otro vértice de la propia comunidad y la probabilidad de
Que un enlace tenga como origen y destino dicha comunidad. Calculando dicha
Probabilidad como el producto de la proporción de enlaces que parten de una

comunidad
Y la de enlaces que llegan a esa comunidad. En el caso de redes no dirigidas
Dichas proporciones coinciden. Y en el caso de redes ponderadas, para el
Cálculo de la proporción se utiliza el peso de cada enlace.