DBLPNetworkAnalysis.java

package org.example;

import org.graphstream.algorithm.Toolkit;
import org.graphstream.graph.*;
import org.graphstream.graph.implementations.*;
import org.graphstream.stream.file.FileSourceEdge;
import org.graphstream.algorithm.generator.BarabasiAlbertGenerator;

import java.io.FileWriter;
import java.util.*;

public class DBLPNetworkAnalysis {
    public static void main(String[] args) throws Exception {
        String filePath = "C:/Users/celia/IdeaProjects/TP_RI/com-dblp.ungraph.txt/com-dblp.ungraph.txt"; // Chemin du fichier d'entrée
        Graph graph = new SingleGraph("DBLP Collaboration Network");

        // --- Chargement des données ---
        FileSourceEdge fileSource = new FileSourceEdge();
        fileSource.addSink(graph);

        try {
            fileSource.readAll(filePath);
        } finally {
            fileSource.removeSink(graph);
        }

        // --- Mesures de base ---
        int nodeCount = graph.getNodeCount();
        int edgeCount = graph.getEdgeCount();
        double averageDegree = Toolkit.averageDegree(graph);
        double clusteringCoefficient = Toolkit.averageClusteringCoefficient(graph);
        double randomClusteringCoefficient = averageDegree / nodeCount;
        boolean isConnected = Toolkit.isConnected(graph);
        double minAverageDegreeForConnectivity = Math.log(nodeCount);

        // --- Calcul de la distribution des degrés ---
        calculateDegreeDistribution(graph, "degree_distribution.txt");

        // --- Distance moyenne et distribution des distances ---
        double averageDistance = estimateAverageDistance(graph, 1000);
        exportDistanceDistribution(graph, "distance_distribution.txt", 1000);

        // --- Affichage des résultats ---
        System.out.println("Nombre de noeuds : " + nodeCount);
        System.out.println("Nombre de liens : " + edgeCount);
        System.out.println("Degré moyen : " + averageDegree);
        System.out.println("Coefficient de clustering (réel) : " + clusteringCoefficient);
        System.out.println("Coefficient de clustering (aléatoire) : " + randomClusteringCoefficient);
        System.out.println("Le réseau est-il connexe ? : " + (isConnected ? "Oui" : "Non"));
        System.out.println("Degré moyen minimal pour qu'un graphe aléatoire soit connexe : " + minAverageDegreeForConnectivity);
        System.out.println("Distance moyenne estimée : " + averageDistance);

        // --- Génération et comparaison des réseaux aléatoires et Barabasi-Albert ---
        compareWithGeneratedNetworks(nodeCount, edgeCount, averageDegree);

        // --- Génération d'un réseau selon la méthode de copie ---
        Graph copyModelGraph = generateCopyModelGraph(nodeCount, averageDegree, 0.1);
        System.out.println("\nRéseau généré avec la méthode de copie :");
        printGraphMeasures(copyModelGraph);
    }

    // --- Calcul de la distribution des degrés ---
    public static void calculateDegreeDistribution(Graph graph, String outputFile) throws Exception {
        Map<Integer, Integer> degreeCounts = new HashMap<>();

        for (Node node : graph) {
            int degree = node.getDegree();
            degreeCounts.put(degree, degreeCounts.getOrDefault(degree, 0) + 1);
        }

        int totalNodes = graph.getNodeCount();

        try (FileWriter writer = new FileWriter(outputFile)) {
            writer.write("Degree\tProbability\n");
            for (Map.Entry<Integer, Integer> entry : degreeCounts.entrySet()) {
                double probability = (double) entry.getValue() / totalNodes;
                writer.write(entry.getKey() + "\t" + probability + "\n");
            }
        }

        System.out.println("Distribution des degrés exportée dans : " + outputFile);
    }

    // --- Estimation de la distance moyenne ---
    public static double estimateAverageDistance(Graph graph, int sampleSize) {
        List<Node> nodes = new ArrayList<>();
        graph.nodes().forEach(nodes::add);
        Random random = new Random();
        double totalDistance = 0;
        int count = 0;

        // Échantillonner au maximum 1000 nœuds ou la taille totale du graphe
        int actualSampleSize = Math.min(sampleSize, nodes.size());

        for (int i = 0; i < actualSampleSize; i++) {
            Node start = nodes.get(random.nextInt(nodes.size()));
            Map<Node, Integer> distances = bfsDistances(graph, start, 50); // Limite de profondeur
            for (int distance : distances.values()) {
                totalDistance += distance;
                count++;
            }
        }

        return totalDistance / count;
    }

    // --- Exportation de la distribution des distances ---
    public static void exportDistanceDistribution(Graph graph, String outputFile, int sampleSize) throws Exception {
        Map<Integer, Integer> distanceCounts = new HashMap<>();
        List<Node> nodes = new ArrayList<>();
        graph.nodes().forEach(nodes::add);
        Random random = new Random();

        // Échantillonner au maximum 1000 nœuds ou la taille totale du graphe
        int actualSampleSize = Math.min(sampleSize, nodes.size());

        for (int i = 0; i < actualSampleSize; i++) {
            Node start = nodes.get(random.nextInt(nodes.size()));
            Map<Node, Integer> distances = bfsDistances(graph, start, 100);

            for (int distance : distances.values()) {
                distanceCounts.put(distance, distanceCounts.getOrDefault(distance, 0) + 1);
            }
        }

        try (FileWriter writer = new FileWriter(outputFile)) {
            writer.write("Distance\tFrequency\n");

            for (Map.Entry<Integer, Integer> entry : distanceCounts.entrySet()) {
                writer.write(entry.getKey() + "\t" + entry.getValue() + "\n");
            }
        }

        System.out.println("Distribution des distances exportée dans : " + outputFile);
    }

    // --- BFS pour calculer les distances ---
    public static Map<Node, Integer> bfsDistances(Graph graph, Node start, int maxDepth) {
        Map<Node, Integer> distances = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        distances.put(start, 0);
        queue.add(start);

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            int currentDistance = distances.get(current);

            if (currentDistance >= maxDepth) continue;

            current.edges().forEach(edge -> {
                Node neighbor = edge.getOpposite(current);
                if (!distances.containsKey(neighbor)) {
                    distances.put(neighbor, currentDistance + 1);
                    queue.add(neighbor);
                }
            });
        }

        return distances;
    }

    // --- Comparaison avec des réseaux générés ---
    public static void compareWithGeneratedNetworks(int nodeCount, int edgeCount, double averageDegree) {
        Graph randomGraph = createRandomGraph(nodeCount, edgeCount);

        // Générer un graphe Barabasi-Albert avec le même degré moyen
        int edgesPerNode = (int) Math.round(averageDegree / 2);
        Graph baGraph = generateBarabasiAlbertGraph(nodeCount, edgesPerNode);

        System.out.println("\nR\u00e9seau al\u00e9atoire :");
        printGraphMeasures(randomGraph);

        System.out.println("\nR\u00e9seau Barabasi-Albert :");
        printGraphMeasures(baGraph);
    }

    // --- Génération d'un réseau aléatoire ---
    public static Graph createRandomGraph(int nodeCount, int edgeCount) {
        Graph randomGraph = new SingleGraph("Random Network");
        Random random = new Random();

        for (int i = 0; i < nodeCount; i++) {
            randomGraph.addNode(String.valueOf(i));
        }

        Set<String> edges = new HashSet<>();

        while (randomGraph.getEdgeCount() < edgeCount) {
            int source = random.nextInt(nodeCount);
            int target = random.nextInt(nodeCount);

            if (source != target) {
                String edge = source + "-" + target;
                String reverseEdge = target + "-" + source;

                if (!edges.contains(edge) && !edges.contains(reverseEdge)) {
                    randomGraph.addEdge(edge, String.valueOf(source), String.valueOf(target));
                    edges.add(edge);
                }
            }
        }

        return randomGraph;
    }

    // --- Génération d'un réseau Barabasi-Albert ---
    public static Graph generateBarabasiAlbertGraph(int nodeCount, double averageDegree) {
        int edgesPerNode = (int) Math.round(averageDegree *2); // Calculez m correctement
        Graph graph = new SingleGraph("Barabasi-Albert Network");
        BarabasiAlbertGenerator generator = new BarabasiAlbertGenerator(edgesPerNode);

        generator.addSink(graph);
        generator.begin();

        while (graph.getNodeCount() < nodeCount) {
            generator.nextEvents();
        }

        generator.end();
        return graph;
    }

    // --- Génération d'un réseau selon la méthode de copie ---
    public static Graph generateCopyModelGraph(int nodeCount, double averageDegree, double probability) {
        Graph copyGraph = new SingleGraph("Copy Model Network");
        Random random = new Random();

        copyGraph.addNode("0");

        for (int i = 1; i < nodeCount; i++) {
            copyGraph.addNode(String.valueOf(i));
            Node targetNode = copyGraph.getNode(String.valueOf(random.nextInt(i)));

            int finalI = i;
            targetNode.neighborNodes().forEach(neighbor -> {
                if (random.nextDouble() < probability) {
                    copyGraph.addEdge(finalI + "-" + neighbor.getId(), String.valueOf(finalI), neighbor.getId());
                }
            });

            copyGraph.addEdge(i + "-" + targetNode.getId(), String.valueOf(i), targetNode.getId());
        }

        return copyGraph;
    }

    // --- Affichage des mesures d'un graphe ---
    public static void printGraphMeasures(Graph graph) {
        System.out.println("Nombre de n\u0153uds : " + graph.getNodeCount());
        System.out.println("Nombre de liens : " + graph.getEdgeCount());
        System.out.println("Degr\u00e9 moyen : " + Toolkit.averageDegree(graph));
        System.out.println("Coefficient de clustering : " + Toolkit.averageClusteringCoefficient(graph));
        System.out.println("Distance moyenne estim\u00e9e : " + estimateAverageDistance(graph, 100));
    }
}