On cherche à maximiser l'entropie globalement sur un graphe donné c'est à dire sur toutes les trajectoires possibles. Lorsque le graphe est fini on peut montrer aisément qu'un tel processus est défini de manière unique : on l'appelle « la marche aléatoire maximale entropique ». Cependant, il est très difficile d'expliciter les probabilités de transition ainsi que la mesure invariante de cette chaîne de Markov. En effet, ces quantités dépendent du spectre de la matrice d'adjacence du graphe et plus précisément du rayon spectral et du vecteur propre associé à celui-ci.
Dans cet exposé, on définira donc le modèle général de cette marche, en observant quelques propriétés caractéristiques de la marche. Puis un intérêt sera porté sur le cas des graphes infinis, en particulier à travers l'exemple d'un graphe araignée, où ni l'existence ni l'unicité ne sont garantis. Sur ces derniers, on pourra naturellement effectuer des limites d'échelles de cette marche aléatoire et reconnaître des processus limites classiques. On donnera aussi quelques applications de cette marche aléatoire : prédiction de liens, détection de contours...