102:
377:
31:
89:. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is. It has been used in analyzing the robustness and
449:
654:, as pictured. The squared values of the components of the Fiedler vector, summing up to one since the vector is normalized, can be interpreted as probabilities of the corresponding data points to be assigned to the sign-based partition.
196:
262:
307:, defined by local configurations whose removal would disconnect the graph, the algebraic connectivity is dependent on the global number of vertices, as well as the way in which vertices are connected. In
1035:
590:
731:
Even if G is quasi-strongly connected, which is equivalent to G containing a directed spanning tree, a(G) can still be nonpositive as the exploding star and
Theorem 1 indicate.
652:
522:
322:
has developed an extensive theory using a rescaled version of the
Laplacian, eliminating the dependence on the number of vertices, so that the bounds are somewhat different.
298:
333:, the Laplacian matrix arises naturally, so the algebraic connectivity gives an indication of how easily the network will synchronize. Other measures, such as the average
387:
154:
300:. For the graph with 6 nodes show above (n=6,D=3) these bound means, 4/18 = 0.222 ≤ algebraic connectivity 0.722 ≤ connectivity 1.
156:
with the inequality being strict if and only if G is connected. However, the algebraic connectivity can be negative for general directed graphs, even if
337:(characteristic path length) can also be used, and in fact the algebraic connectivity is closely related to the (reciprocal of the) average distance.
834:
Graph Theory, Combinatorics, and
Applications. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs
524:. Alternatively, the value of 0.069 (which is close to zero) can be placed in a class of its own, partitioning the graph into three components:
171:
227:
969:
934:
885:
799:
1073:
265:
63:
1078:
663:
165:
114:
39:
1083:
304:
334:
217:
35:
527:
312:
106:
595:
465:
341:
271:
110:
444:{\textstyle {\begin{pmatrix}0.415&0.309&0.069&-0.221&0.221&-0.794\end{pmatrix}}}
164:. Furthermore, the value of the algebraic connectivity is bounded above by the traditional (vertex)
311:, the algebraic connectivity decreases with the number of vertices, and increases with the average
905:
722:
710:
452:
17:
856:
212:). If the number of vertices of an undirected connected graph with nonnegative edge weights is
124:
965:
940:
930:
881:
829:
795:
764:
451:. The negative values are associated with the poorly connected vertex 6, and the neighbouring
90:
959:
1047:
1016:
998:
875:
837:
787:
756:
714:
353:
74:
59:
1012:
318:
The exact definition of the algebraic connectivity depends on the type of
Laplacian used.
1020:
1008:
841:
688:
365:
326:
161:
86:
668:
330:
199:
892:
340:
The algebraic connectivity also relates to other connectivity attributes, such as the
1067:
726:
455:, vertex 4; while the positive values are associated with the other vertices. The
308:
822:
818:
357:
904:
Pereira, Tiago (2011). "Stability of
Synchronized Motion in Complex Networks".
718:
70:
1003:
986:
768:
760:
944:
880:. Regional Conference Series in Mathematics. Vol. 92. Amer. Math. Soc.
319:
744:
121:
The algebraic connectivity of undirected graphs with nonnegative weights,
101:
384:
For the example graph in the introductory section, the
Fiedler vector is
191:{\displaystyle {\text{algebraic connectivity}}\leq {\text{connectivity}}}
1052:
352:
The original theory related to algebraic connectivity was produced by
376:
257:{\displaystyle {\text{algebraic connectivity}}\geq {\frac {1}{nD}}}
791:
462:
can therefore be used to partition this graph into two components:
30:
910:
701:
Wu, Chai Wai (2005). "Algebraic connectivity of directed graphs".
375:
224:, the algebraic connectivity is also known to be bounded below by
100:
198:, unless the graph is complete (the algebraic connectivity of a
857:"Synchronization and Connectivity of Discrete Complex Systems"
360:
associated with the algebraic connectivity has been named the
964:(2nd ed.). Cambridge University Press. pp. 28, 58.
344:, which is bounded below by half the algebraic connectivity.
598:
530:
468:
396:
390:
274:
230:
174:
127:
81:. This eigenvalue is greater than 0 if and only if
646:
584:
516:
443:
292:
256:
190:
148:
73:(counting multiple eigenvalues separately) of the
1036:"Laplacian of graphs and algebraic connectivity"
27:Second-smallest eigenvalue of a graph Laplacian
372:Partitioning a graph using the Fiedler vector
117:of 3, and an algebraic connectivity of 0.243.
8:
641:
623:
617:
599:
579:
567:
561:
555:
549:
531:
511:
499:
493:
469:
927:Six Degrees: The Science of a Connected Age
861:International Conference on Complex Systems
691:." From MathWorld--A Wolfram Web Resource.
1051:
1002:
909:
597:
529:
467:
391:
389:
275:
273:
239:
231:
229:
183:
175:
173:
126:
836:. Vol. 2. Wiley. pp. 871–898.
29:
813:
811:
680:
380:Partitioning into two connected graphs.
782:Gross, J.L.; Yellen, J., eds. (2004).
305:traditional form of graph connectivity
364:. The Fiedler vector can be used to
7:
585:{\textstyle \{1,2,5\},\{3\},\{4,6\}}
460:of the values in the Fiedler vector
42:1, and algebraic connectivity 0.722
34:An example graph, with 6 vertices,
987:"Algebraic connectivity of Graphs"
823:"The Laplacian Spectrum of Graphs"
745:"Algebraic connectivity of graphs"
264:, and in fact (in a result due to
25:
991:Czechoslovak Mathematical Journal
749:Czechoslovak Mathematical Journal
18:Algebraic connectivity of a graph
647:{\textstyle \{1,2,5\},\{3,4,6\}}
592:or moved to the other partition
517:{\textstyle \{1,2,3,5\},\{4,6\}}
828:. In Alavi, Y.; Chartrand, G.;
293:{\displaystyle {\frac {4}{nD}}}
703:Linear and Multilinear Algebra
137:
131:
1:
664:Connectivity (graph theory)
1100:
1040:Banach Center Publications
893:Incomplete revised edition
786:. CRC Press. p. 571.
743:Fiedler, Miroslav (1973).
149:{\displaystyle a(G)\geq 0}
855:Holroyd, Michael (2006).
719:10.1080/03081080500054810
329:on networks, such as the
1004:10.21136/CMJ.1973.101168
832:; Schwenk, A.J. (eds.).
784:Handbook of Graph Theory
761:10.21136/cmj.1973.101168
113:graph has a traditional
233:algebraic connectivity
69:is the second-smallest
1074:Algebraic graph theory
961:Algebraic Graph Theory
958:Biggs, Norman (1993).
874:Chung, F.R.K. (1997).
689:Algebraic Connectivity
648:
586:
518:
445:
381:
294:
258:
192:
177:algebraic connectivity
150:
118:
48:algebraic connectivity
43:
1034:Fiedler, M. (1989) .
877:Spectral Graph Theory
649:
587:
519:
446:
379:
295:
259:
193:
151:
107:truncated icosahedron
104:
33:
985:Fiedler, M. (1973).
687:Weisstein, Eric W. "
596:
528:
466:
388:
342:isoperimetric number
272:
228:
172:
125:
111:Buckminsterfullerene
1053:10.4064/-25-1-57-70
356:. In his honor the
1079:Graph connectivity
925:Watts, D. (2003).
711:Taylor and Francis
644:
582:
514:
453:articulation point
441:
435:
382:
290:
254:
188:
146:
119:
56:Fiedler eigenvalue
44:
288:
252:
234:
186:
178:
91:synchronizability
16:(Redirected from
1091:
1084:Graph invariants
1058:
1057:
1055:
1031:
1025:
1024:
1006:
982:
976:
975:
955:
949:
948:
922:
916:
915:
913:
901:
895:
891:
871:
865:
864:
852:
846:
845:
830:Oellermann, O.R.
827:
815:
806:
805:
779:
773:
772:
740:
734:
733:
698:
692:
685:
653:
651:
650:
645:
591:
589:
588:
583:
523:
521:
520:
515:
450:
448:
447:
442:
440:
439:
354:Miroslav Fiedler
299:
297:
296:
291:
289:
287:
276:
263:
261:
260:
255:
253:
251:
240:
235:
232:
211:
207:
197:
195:
194:
189:
187:
184:
179:
176:
155:
153:
152:
147:
75:Laplacian matrix
60:Miroslav Fiedler
21:
1099:
1098:
1094:
1093:
1092:
1090:
1089:
1088:
1064:
1063:
1062:
1061:
1033:
1032:
1028:
997:(98): 298–305.
984:
983:
979:
972:
957:
956:
952:
937:
924:
923:
919:
903:
902:
898:
888:
873:
872:
868:
854:
853:
849:
825:
817:
816:
809:
802:
781:
780:
776:
742:
741:
737:
700:
699:
695:
686:
682:
677:
660:
594:
593:
526:
525:
464:
463:
434:
433:
425:
420:
412:
407:
402:
392:
386:
385:
374:
350:
327:synchronization
280:
270:
269:
244:
226:
225:
209:
206:
202:
170:
169:
162:connected graph
123:
122:
99:
87:connected graph
50:(also known as
28:
23:
22:
15:
12:
11:
5:
1097:
1095:
1087:
1086:
1081:
1076:
1066:
1065:
1060:
1059:
1026:
977:
970:
950:
935:
917:
896:
886:
866:
847:
807:
800:
792:10.1201/b16132
774:
755:(2): 298–305.
735:
693:
679:
678:
676:
673:
672:
671:
669:Graph property
666:
659:
656:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
581:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
539:
536:
533:
513:
510:
507:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
438:
432:
429:
426:
424:
421:
419:
416:
413:
411:
408:
406:
403:
401:
398:
397:
395:
373:
370:
362:Fiedler vector
349:
348:Fiedler vector
346:
331:Kuramoto model
286:
283:
279:
250:
247:
243:
238:
204:
200:complete graph
182:
145:
142:
139:
136:
133:
130:
98:
95:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1096:
1085:
1082:
1080:
1077:
1075:
1072:
1071:
1069:
1054:
1049:
1045:
1041:
1037:
1030:
1027:
1022:
1018:
1014:
1010:
1005:
1000:
996:
992:
988:
981:
978:
973:
971:0-521-45897-8
967:
963:
962:
954:
951:
946:
942:
938:
936:0-434-00908-3
932:
928:
921:
918:
912:
907:
900:
897:
894:
889:
887:0-8218-8936-2
883:
879:
878:
870:
867:
862:
858:
851:
848:
843:
839:
835:
831:
824:
820:
814:
812:
808:
803:
801:0-203-49020-7
797:
793:
789:
785:
778:
775:
770:
766:
762:
758:
754:
750:
746:
739:
736:
732:
728:
724:
720:
716:
712:
708:
704:
697:
694:
690:
684:
681:
674:
670:
667:
665:
662:
661:
657:
655:
638:
635:
632:
629:
626:
620:
614:
611:
608:
605:
602:
576:
573:
570:
564:
558:
552:
546:
543:
540:
537:
534:
508:
505:
502:
496:
490:
487:
484:
481:
478:
475:
472:
461:
459:
454:
436:
430:
427:
422:
417:
414:
409:
404:
399:
393:
378:
371:
369:
367:
363:
359:
355:
347:
345:
343:
338:
336:
332:
328:
325:In models of
323:
321:
316:
314:
310:
309:random graphs
306:
301:
284:
281:
277:
267:
266:Brendan McKay
248:
245:
241:
236:
223:
219:
215:
208:is its order
201:
180:
167:
163:
159:
143:
140:
134:
128:
116:
112:
108:
103:
96:
94:
93:of networks.
92:
88:
84:
80:
76:
72:
68:
65:
61:
57:
53:
52:Fiedler value
49:
41:
37:
32:
19:
1046:(1): 57–70.
1043:
1039:
1029:
994:
990:
980:
960:
953:
926:
920:
899:
876:
869:
860:
850:
833:
819:Mohar, Bojan
783:
777:
752:
748:
738:
730:
706:
702:
696:
683:
457:
456:
383:
361:
351:
339:
324:
317:
302:
221:
213:
185:connectivity
168:of a graph,
166:connectivity
157:
120:
115:connectivity
82:
78:
66:
55:
51:
47:
45:
40:connectivity
929:. Vintage.
713:: 203–223.
358:eigenvector
303:Unlike the
1068:Categories
1021:0265.05119
842:0840.05059
675:References
368:a graph.
97:Properties
71:eigenvalue
911:1112.2297
769:0011-4642
727:121368189
428:−
415:−
366:partition
320:Fan Chung
237:≥
181:≤
141:≥
945:51622138
821:(1991).
658:See also
335:distance
218:diameter
216:and the
36:diameter
1013:0318007
62:) of a
1019:
1011:
968:
943:
933:
884:
840:
798:
767:
725:
313:degree
58:after
906:arXiv
826:(PDF)
723:S2CID
709:(3).
458:signs
431:0.794
423:0.221
418:0.221
410:0.069
405:0.309
400:0.415
268:) by
160:is a
85:is a
64:graph
966:ISBN
941:OCLC
931:ISBN
882:ISBN
796:ISBN
765:ISSN
105:The
46:The
1048:doi
1017:Zbl
999:doi
838:Zbl
788:doi
757:doi
715:doi
220:is
109:or
77:of
54:or
38:3,
1070::
1044:25
1042:.
1038:.
1015:.
1009:MR
1007:.
995:23
993:.
989:.
939:.
859:.
810:^
794:.
763:.
753:23
751:.
747:.
729:.
721:.
707:53
705:.
315:.
1056:.
1050::
1023:.
1001::
974:.
947:.
914:.
908::
890:.
863:.
844:.
804:.
790::
771:.
759::
717::
642:}
639:6
636:,
633:4
630:,
627:3
624:{
621:,
618:}
615:5
612:,
609:2
606:,
603:1
600:{
580:}
577:6
574:,
571:4
568:{
565:,
562:}
559:3
556:{
553:,
550:}
547:5
544:,
541:2
538:,
535:1
532:{
512:}
509:6
506:,
503:4
500:{
497:,
494:}
491:5
488:,
485:3
482:,
479:2
476:,
473:1
470:{
437:)
394:(
285:D
282:n
278:4
249:D
246:n
242:1
222:D
214:n
210:n
205:n
203:K
158:G
144:0
138:)
135:G
132:(
129:a
83:G
79:G
67:G
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
