Abstract-I detta dokument visar vi en fas övergångsfenomen i algebraisk anslutning av små-världsnätverk. Algebraisk anslutning av en graf är det näst minsta eigenvärdet av dess Laplaciska matris och ett mått på hastigheten för att lösa konsensusproblem i nätverk. Vi visar att det är möjligt att dramatiskt öka den algebraiska anslutningen av ett regelbundet komplext nätverk med 1000 gånger eller mer utan att lägga till nya länkar eller noder till nätverket. Detta innebär att ett samförståndsproblem kan lösas otroligt snabbt på vissa småvärldsnät som ger upphov till en nätverksdesignalgoritm för ultrasnabba informationsnät. Vår studie bygger på ett förfarande som kallas "random rewiring" på grund av Watts & Strogatz (Natur, 1998). Omfattande numeriska resultat tillhandahålls för att stödja våra påståenden och antaganden. Vi bevisar att medelvärdet av det stora Laplaciska spektrumet av ett komplext nätverk fortfarande är invariant under slumpmässig omkoppling. Samma egenskap äger endast asymptotiskt för skalfria nät. Ett samband mellan att öka den algebraiska anslutningen av komplexa nätverk och robustheten att länka och nodfel visas också. Detta är ett alternativ till användning av perkoleringsteori för analys av nätets robusthet. Vi visar också några kopplingar mellan våra gissningar och vissa öppna problem i teorin om slumpmässiga matriser.
Olfati-Saber REF visade att det är möjligt att dramatiskt öka det näst största eigenvärdet av Laplacian-matrisen i en regelbunden graf genom att vrida om vissa kanter, utan att avsevärt minska det största eigenvärdet.
Ultrafast consensus in small-world networks
{'venue': 'Proceedings of the 2005, American Control Conference, 2005.', 'journal': 'Proceedings of the 2005, American Control Conference, 2005.', 'mag_field_of_study': ['Computer Science']}