Generando gráficos favoreciendo cliques únicos
Para un proyecto de investigación en el que estoy trabajando, necesito generar grafos aleatorios que favorezcan la formación de cliques sin que los cliques más grandes contengan los mismos nodos. Por ejemplo, el modelo Barabási-Albert puede generar grafos que contienen grandes cliques, pero esos cliques tienen principalmente los mismos nodos debido a la unión preferencial.
Aunque prefiero usar paquetes existentes como Networkx o IGraph, estoy dispuesto a implementar documentos de investigación que hayan formalizado la generación de dichas redes. El único criterio es que la generación de esos grafos no debería llevar más de 15 segundos para un grafo con, por ejemplo, 10.000 nodos y un grado promedio de 100.
Tampoco estoy seguro si debo hacer esta pregunta aquí o en https://math.stackexchange.com/, así que díganme si necesito preguntarlo allí.
davy.ai
Como experto en IT especializado en Python, C++, Networkx, teoría de grafos e igraph, puedo sugerir algunas soluciones para tu proyecto de investigación.
Un enfoque posible es utilizar el modelo Erdős-Rényi, que genera grafos con un número predefinido de nodos y aristas. Este modelo conecta los nodos al azar con igual probabilidad, y puedes ajustar la probabilidad para favorecer la formación de cliques. Sin embargo, este modelo puede producir grafos con cliques grandes que contienen los mismos nodos, por lo que necesitas aplicar algún postprocesamiento para eliminar dichos cliques.
Otro enfoque es utilizar el modelo de bloques estocásticos (Stochastic Block Model, SBM), que genera grafos con grupos de nodos. Dentro de cada grupo, los nodos tienen más probabilidades de estar conectados entre sí, pero entre grupos, la probabilidad de conexiones es menor. Ajustando los parámetros del modelo puedes generar grafos que favorezcan la formación de cliques limitando las superposiciones entre los cliques más grandes.
Networkx e igraph tienen funciones incorporadas para generar grafos con SBM, como networkx.generators.community.stochastic_block_model e igraph.Graph.Block. También puedes encontrar varios artículos de investigación sobre SBM, como “Community Detection in Graphs” de Fortunato y “Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters” de Clauset et al.
En cuanto al requisito de tiempo de generación, es factible generar grafos con 10,000 nodos y un grado promedio de 100 en 15 segundos utilizando implementaciones optimizadas. Sin embargo, el tiempo exacto depende del hardware, el software y los parámetros del modelo.
En cuanto a si debes hacer esta pregunta aquí o en math.stackexchange.com, depende de si buscas respuestas más teóricas o prácticas. Dado que tu pregunta implica programación e implementación de algoritmos, este foro es un lugar adecuado para hacerla. Sin embargo, si necesitas perspectivas o pruebas matemáticas adicionales, también puedes hacerla en math.stackexchange.com.
Espero que esto responda tu pregunta, y no dudes en pedir más detalles o aclaraciones.