Wolfram Computation Meets Knowledge

21 Graphs and Networks

21Graphs and Networks
A graph is a way of showing connections between thingssay, how webpages are linked, or how people form a social network.
A very simple graph of connections:
Graph[{1 -> 2, 2 -> 3, 3 -> 4}]
 
Automatically label all the “vertices”:
Graph[{1 -> 2, 2 -> 3, 3 -> 4}, VertexLabels -> All]
 
Let’s add one more connection: to connect 4 to 1. Now we have a loop.
Add another connection, forming a loop:
Graph[{1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1}, VertexLabels -> All]
 
Add two more connections, including one connecting 2 right back to 2:
Graph[{1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1, 3 -> 1, 2 -> 2}, VertexLabels -> All]
 
A different layout of the same graph (check by tracing the connections):
Graph[{1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1, 3 -> 1, 2 -> 2}, VertexLabels -> All, GraphLayout -> "RadialDrawing"]
 
You can do computations on the graph, say finding the shortest path that gets from 4 to 2, always following the arrows.
The shortest path from 4 to 2 on the graph goes through 1:
FindShortestPath[ Graph[{1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1, 3 -> 1, 2 -> 2}], 4, 2]
 
Now let’s make another graph. This time let’s have 3 nodes, and let’s have a connection between every one of them.
Start by making an array of all possible connections between 3 objects:
Table[i -> j, {i, 3}, {j, 3}]
 
The result here is a list of lists. But what Graph needs is just a single list of connections. We can get that by using Flatten to “flatten” out the sublists.
Flatten “flattens out” all sublists, wherever they appear:
Flatten[{{a, b}, 1, 2, 3, {x, y, {z}}}]
 
Get a “flattened” list of connections from the array:
Flatten[Table[i -> j, {i, 3}, {j, 3}]]
 
Graph[Flatten[Table[i -> j, {i, 3}, {j, 3}]], VertexLabels -> All]
 
Generate the completely connected graph with 6 nodes:
Graph[Flatten[Table[i -> j, {i, 6}, {j, 6}]]]
 
Sometimes the “direction” of a connection doesn’t matter, so we can drop the arrows.
The “undirected” version of the graph:
UndirectedGraph[Flatten[Table[i -> j, {i, 6}, {j, 6}]]]
 
Make a graph with 20 connections between randomly chosen nodes numbered from 0 to 10:
Graph[Table[RandomInteger[10] -> RandomInteger[10], 20], VertexLabels -> All]
 
You’ll get a different graph if you generate different random numbers. Here are 6 graphs.
Six randomly generated graphs:
Table[Graph[Table[RandomInteger[10] -> RandomInteger[10], 20]], 6]
 
CommunityGraphPlot[\!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{18, 17, 14, 12, 4, 2, 1, 11, 6, 16, 13, 0, 10, 15, 20, 7, 5, 8, 9, 3, 19}, {{{1, 2}, {1, 3}, {4, 5}, {6, 1}, {7, 6}, {3, 7}, {8, 3}, {9, 10}, {6, 11}, {12, 7}, {9, 13}, {9, 4}, {14, 9}, {10, 15}, {4, 13}, {14, 2}, {10, 11}, {3, 12}, {10, 9}, { 9, 7}, {16, 16}, {17, 1}, {2, 5}, {10, 14}, {2, 10}, {18, 13}, {17, 19}, {4, 6}, {2, 4}, {12, 10}, {12, 8}, {4, 20}, { 15, 12}, {6, 11}, {2, 15}, {19, 1}, {20, 9}, {15, 10}, {1, 2}, {17, 6}, {6, 14}, {5, 14}, {12, 7}, {14, 7}, {9, 8}, {6, 11}, {3, 21}, {18, 15}, {13, 16}, {5, 8}}, Null}]]}, TagBox[GraphicsGroupBox[GraphicsComplexBox[CompressedData[" 1:eJw9Vgk01O33n/nOmLF8v8PY15cQqV9eLZYkzyVlaRFF2QslQmSXFkp4E0mU QomS9FraUC8jO0kpsrxFCRWyzJgRNc1//uf8zu+e85x7Puc893PufZ67LfM+ 6ngQI5FIncLz/zq1vdl3f7Y0cC8mNqY3/kbntR0Nk5fEIDnVIfX7rt8Ibpgm H//BBNqKi96yZ78hWlnqxcs/MUi6YiLhJ/8DPQ9KjIo6QoeZwJxl+hJTyH/c PMYsjQG0+fbZzz0k2C1l/XdTPQGsjK6B6SdzSNo/SuP4vAT0zFrXr2v8iGQm V5hJj1LAyKSW6vJiDu1YH6BVWUEHZ0tG7Y1+MrAIm4RAdRxmjd0id7wVBcNC j71XhHjZWOeLqMgFdGaTV7puFAd9KwzwN8v/gTLG6qVaXomCvDhn7surBYSX d/k+0qVA/aFj38VzMCD9V8yzfbKmiAXEPfxF5Y8FGVhYu3ps2JkKTasKYt0y OQjTvGXin0OBpptZ6RMseThZ4m3uGU6B1UOlaRSHn8jqutuXuVtjaO7wvtkX L+X+xytul2chS5KGgOB16mmf+eh3HsmtdoAJn1viizLL+IhOOd7R9YAJhz8c 9hCN56NEjJnndZ4J57J0LOhufOTn8X1Vkg8TqoZ0X98x46OfMmkMj41MWCv1 hLa4nI8+nevEF6WZYNC5y1FCgY+O89qkwiakILb6acq4JB+xObFK/q4EnD6D CHzkF7ofHqhnK0aAd6rlkUdC3P7ztu2Wahx2vdBP1Zv8hdbCQOgFPxzaU+WC D/38hUqePAx0UMAhyLE+7IAMH80VXXpW3yoB0lLeAfg6PtLP844Vj5GAEStB xh5XPpoUfbbZY5UE7OQl3dVM4SP3vRkfuHyhf7r2xa7nBcj0wiZL9T4m5PX3 1a54KkAuKbeXNZUzIZCIGAv5JEAnSHLtP5OYkHJQYvoCiQQ1GxNaPngxwbXt Y8h5nATfP1wfjDdmgrxez6cSWRIcL6ieEDCYkGZjd2xUkQQDByrZR8elQNC5 rcBEiQRlHds+eDsScGYtw2cbRoKREqsxZzIB9g7n+KF8ASpPf/4prQIHe2KZ 7dlpAer5hRWb7hfGb15+6l2fAOU8eNaUIoXDYlIFI7JGgLIqv/iXPpcAJQhm h2cK0J3j7226wiQg19mp9NtBAcrQKjyuoSsB8uWFBjMGAhS9v0XxNYkBt33G 0wRZZPhaZe++cYgA0yMjVmWtZOiKKnaRrSPgjd7J0YUlMqjabFQOvkmADpqU rPsTg79z5P/jmkgA3iOe/OkgBkqvTlz5GkjA9LPv5pZ5GNivDunV3UtAqtir AFYvBllr5Vu1rQhIHDyRYyxJgcSIhx3UbTjYpDsYtlnQ4N+SusoOUxwq0397 KcXR4EQgS89nNQ7OcQcEGlU0aK8I13ynicPI45Ua/7BpUC+q9K+eCg4WHY+i WvXp4NpcPuQtj0PRw2/R6sI6d/HYQz4ri4NosL3/zWI62D644Jkmh8O9wD8j dUbpMGqxmKt8lQH2LO6seBMZerLXLmnnMGC2tpd/kYTBW/0+1a1XGLAneuM0 cxMGQZNBGqcuMaD6QMiMfwwGPpulB978xQD5yKWtEY8xqEhq7d5ymgG3yhv9 pOYwcLBrsx06xgCbXB264n8oUHzyrUGRNwMqc9+u8T9EgeznIevP+hMQ7lD8 cvEqDd63yOvEOxMQpOn8K/QNDZjLxXzrQfi+IcYrZsTpcNI15NXOFQRM7VUe trekA+P+tk+mBAFvpzbsDYumg3vccMHlGRx0sOKEDX/TwcLM+EbQKxzq6i01 z3ykw4PM+pH++zjsaTPvXyMtCrLlN4ZVeBQYND7UtHKBg5bZrf/h9osCKjzZ xegz8+jJq7N3FkWo8HK+sY0iyUX2W4gNM9JU8JYvvBydw0VRbUkUQy0q2LFO eCdq8hBkRPk8N6JCx34rYqCEh5p2fmhO3kGF6dcKEVp/LiD5E8yyE35UQPya MrkHC6iVdEn8rykRoNvLWPUP/kZX9CyU88RoELeuoFXbTYBWOiUq1+rRQPtI bP6pfgE6baNA69tOA/tsNRt7PRIUJWXIvjtGgyLRvcW5viRwDK1rKbxOA+nu Ha+p+SSoXjnB0W2lwecV5c0He0kQEG3Qb8MV8mtm1OaLk2FHCOdUcT4dEhs2 fHjSQALo9fTzu0oHX5+RhvQ4EtyzZ9S0p9FBYlTcrcOIBNKDiTo98XRIuGM0 of5ZgCacJdzTQulwje+mKuMqQJppKr/InnRQds8KZb35jfJeP84xtaYDd/K5 WMSO32jbrfjKLavpUMhSf53QwUfX/iA7bbgrAu+DWkzrC3iog+uwRee8CPil mFSFLeMhow5iC+2ICNQ7eH1ULOKiT++Ou0xZi4DVxfzpRT0uqr1C3vZ9mQjk lq4y8Ho4jyTLeq6qL1KBpWw+lAbz6N783SPXX1JB9chxTmc3By3c8U6KvUGF qagqipsfB4nuVDnEE9ZNM5tWT28gw/xQ9VMagw5no/u8VGrJYDXVazQ6RQOx 6rW9zTVk2BrQHn3rBQ3eBEQqiVWTYd0pvzVO92hgIzW/bryKDEen9ylKpdCg W8Rpg4fw/uno4I/jfjSQ35a2LegfMmgrLaz6vpUGlYs+12Sfk0FcYUo6OZIK kr37rHEGBnvF5A53O1HhDT+EaSOLwXiY6/JQQyoM23Bvy6pioJklGRkrRwXH Aw2HgpZjIG4qYk0S5u/OT1ovthtg8NTYaaNcHwUm1VV87pthIP2XS8GLagrE zer/e9YOA7mbvX6G1yngwWwgdblg4Cz6ftPAIRzwjt0KY4s85K0VZB0XjUOV ARadPMBDv/ZJzzmm4LDmUI31mSoeGrRIttydg4PiV5HSb5k89GpzeEPYXRzY b748fh3MQ3mZpLjSJziIUfZ57bThoZh6PSq7EYeMN1vDYzR4KPv205PotZBv hepf/gtcZNY9GvRHFCGM44x75z0OerGodulIAgGq47qNOac5SOeJSHllKgHk zJuRHk4ctHuPZ/lEFgExXZZSa/Q4KF4L1Jj5BChNp1bp/2KjEA2n5Rq3CXBq K5EO7WKjwf2PcmRKCdAPKjGSuclG1alu81/KCVhuFH3FIJSN3ujYSoUb4PAP aDGM/uGhCsfZABtDHB6KsYN3X+Ah5Uz74Y0bcThfNneJ68lDohd9v9hZ4tCW zJg2XsNDxl5bnULtcDh8d1+WIZWHDvLzne7txmH485K+WD8XsWrOHZv1wKH5 YthI530u2jnCyt7kj0OfmaLttQQumicmElWlCKjYeUqFb8hBTE4sKUCVgF1F e9Z8xzloWr0ouUKPgL6wzVsVx9jo2VEDy6/GBMwUPpzJqmOjylDVBlFrAtrT spbictgozfWSjJhw3pRLjXh8jmCjFReNa4f9CFi5NWf10G42Wl/a1pIQQ0Dv feu0+HVs5Jilpnm0hAIOT2ImbpVjcIh6+qVnBwUuGZTYpT/CQH7B2yF+kgLE 3I7e0SoMZGOOSjbiVLAyF88oqMFA17fbWUqfCl1XUyObhHhyfviokz0VthSu Ct1RjcFgQEfxyRAqkDzZnpuE88Gow8I9OoMKB8tVpbIrMNjVuT3iwwEa0Ht0 ffJ9MKAMamlcTqCBValkjrcHBuFHh7znb9HAZP95arYTBiY79aQnG2jQZF23 edN2oX3JOouDIzRoa3Uf9rDA4Gbp5+27yHRYlXLQ+vd6DGxchsdz1IX9qdrh 1XJdDLZs9tEw2ESHmit1Je8VhPtl2ZP29EwD5NO/tH2Yz0Mfa2KnXcMjWBCX y6x/z0Vfd8yUJNJusPY2NMUkvZxHdZjb5sZ7D1h/uph38cY4iNtv77Erp56V FyMrUWDCQYxrU+8CFdpZ3RWro4PeslHdprGXJVLdLOW5vJWxwv+aId/f//hk L2tCQ9op4icbiTXdPzcSO8CyRbItsYkclHputsf94XtWNaVmX7TDPOoRDHph 40OswS+bbZn2wvyxlXtUOTbM0tSuWTPtz0Op6kFpX/OGWccqVj/zPL+AjBUc +Ydlh1g3MkcSVuX+QEmBvtqNh/9lKUoG9xw7t4hOSXPVXnb3scb4LT/9jZfQ UgB1wSznLetybKf28M0l9I3P0z+5qotllFjT4/50CVk5v+VTbZpZ1r4uuX3x S8g8JsFT58RTVnGBnWz/z0WkrZZv0fD6Hiv3un6z2rpFpJikpu8Sk8H6Pega 1mD8A5GeurT9fcuE1TZLSZhRW0D/BwNNoyc= "], { {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[0.021710536694215837`], ArrowBox[ BezierCurveBox[{1, {3.9516932575197803`, 1.6786127197810763`}, 2}], 0.046840312738230916`], ArrowBox[ BezierCurveBox[{1, {3.942488939232073, 2.1388895994433716`}, 2}], 0.046840312738230916`], ArrowBox[{1, 3}, 0.046840312738230916`], ArrowBox[{2, 4}, 0.046840312738230916`], ArrowBox[{2, 5}, 0.046840312738230916`], ArrowBox[{2, 10}, 0.046840312738230916`], ArrowBox[{2, 15}, 0.046840312738230916`], ArrowBox[{3, 7}, 0.046840312738230916`], ArrowBox[{3, 12}, 0.046840312738230916`], ArrowBox[{3, 21}, 0.046840312738230916`], ArrowBox[{4, 5}, 0.046840312738230916`], ArrowBox[{4, 6}, 0.046840312738230916`], ArrowBox[{4, 13}, 0.046840312738230916`], ArrowBox[{4, 20}, 0.046840312738230916`], ArrowBox[{5, 8}, 0.046840312738230916`], ArrowBox[{5, 14}, 0.046840312738230916`], ArrowBox[{6, 1}, 0.046840312738230916`], ArrowBox[ BezierCurveBox[{6, {3.5030842254492804`, 2.5535550585345943`}, 11}], 0.046840312738230916`], ArrowBox[{6, 11}, 0.046840312738230916`], ArrowBox[ BezierCurveBox[{6, {3.831710739394434, 2.65357042004921}, 11}], 0.046840312738230916`], ArrowBox[{6, 14}, 0.046840312738230916`], ArrowBox[{7, 6}, 0.046840312738230916`], ArrowBox[{8, 3}, 0.046840312738230916`], ArrowBox[{9, 4}, 0.046840312738230916`], ArrowBox[{9, 7}, 0.046840312738230916`], ArrowBox[{9, 8}, 0.046840312738230916`], ArrowBox[ BezierCurveBox[{9, {2.53987111328563, 1.7495543938902882`}, 10}], 0.046840312738230916`], ArrowBox[{9, 13}, 0.046840312738230916`], ArrowBox[ BezierCurveBox[{10, {2.9077671567847547`, 1.5933644746578552`}, 9}], 0.046840312738230916`], ArrowBox[{10, 11}, 0.046840312738230916`], ArrowBox[{10, 14}, 0.046840312738230916`], ArrowBox[ BezierCurveBox[{10, {2.662381264132733, 2.1845311111714807`}, 15}], 0.046840312738230916`], ArrowBox[ BezierCurveBox[{12, {3.676352478346518, 1.3202886493576447`}, 7}], 0.046840312738230916`], ArrowBox[ BezierCurveBox[{12, {3.558198032323462, 1.253295570504861}, 7}], 0.046840312738230916`], ArrowBox[{12, 8}, 0.046840312738230916`], ArrowBox[{12, 10}, 0.046840312738230916`], ArrowBox[{13, 16}, 0.046840312738230916`], ArrowBox[{14, 2}, 0.046840312738230916`], ArrowBox[{14, 7}, 0.046840312738230916`], ArrowBox[{14, 9}, 0.046840312738230916`], ArrowBox[ BezierCurveBox[{15, {2.6932811430138037`, 2.3709701896509108`}, 10}], 0.046840312738230916`], ArrowBox[{15, 12}, 0.046840312738230916`], ArrowBox[ BezierCurveBox[{16, 185, 188, 190, 196, 198, 201, 16}, SplineDegree->7], 0.046840312738230916`], ArrowBox[{17, 1}, 0.046840312738230916`], ArrowBox[{17, 6}, 0.046840312738230916`], ArrowBox[{17, 19}, 0.046840312738230916`], ArrowBox[{18, 13}, 0.046840312738230916`], ArrowBox[{18, 15}, 0.046840312738230916`], ArrowBox[{19, 1}, 0.046840312738230916`], ArrowBox[{20, 9}, 0.046840312738230916`]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.046840312738230916], DiskBox[2, 0.046840312738230916], DiskBox[3, 0.046840312738230916], DiskBox[4, 0.046840312738230916], DiskBox[5, 0.046840312738230916], DiskBox[6, 0.046840312738230916], DiskBox[7, 0.046840312738230916], DiskBox[8, 0.046840312738230916], DiskBox[9, 0.046840312738230916], DiskBox[10, 0.046840312738230916], DiskBox[11, 0.046840312738230916], DiskBox[12, 0.046840312738230916], DiskBox[13, 0.046840312738230916], DiskBox[14, 0.046840312738230916], DiskBox[15, 0.046840312738230916], DiskBox[16, 0.046840312738230916], DiskBox[17, 0.046840312738230916], DiskBox[18, 0.046840312738230916], DiskBox[19, 0.046840312738230916], DiskBox[20, 0.046840312738230916], DiskBox[21, 0.046840312738230916]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->{"NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FrameTicks->None, GridLinesStyle->Directive[ GrayLevel[0.5, 0.4]], ImageSize->{320.4296875, Automatic}]\)]
 
The result is a graph with the exact same connections as the original, but with the nodes arranged to illustrate the “community structure” of the graph.
Graph[{ij,...}] a graph or network of connections
UndirectedGraph[{ij, ...}] a graph with no directions to connections
VertexLabels an option for what vertex labels to include (e.g. All)
FindShortestPath[graph,a,b] find the shortest path from one node to another
CommunityGraphPlot[list] display a graph arranged into “communities”
Flatten[list] flatten out sublists in a list
21.1Make a graph consisting of a loop of 3 nodes. »
Expected output:
Out[]=
21.2Make a graph with 4 nodes in which every node is connected. »
Expected output:
Out[]=
21.3Make a table of undirected graphs with between 2 and 10 nodes in which every node is connected. »
Expected output:
Out[]=
21.4Use Table and Flatten to get {1, 2, 1, 2, 1, 2}»
Expected output:
Out[]=
Expected output:
Out[]=
Expected output:
Out[]=
21.7Make a graph with 4 nodes, in which each connection connects i to Max[i, j]»
Expected output:
Out[]=
21.8Make a graph in which each connection connects i to j-i, where i and j both range from 1 to 5. »
Expected output:
Out[]=
21.9Generate a graph with 100 nodes, each with a connection going to one randomly chosen node. »
Sample expected output:
Out[]=
21.10Generate a graph with 100 nodes, each connecting to two randomly chosen nodes. »
Sample expected output:
Out[]=
21.11For the graph {12, 23, 34, 41, 31, 22}, make a grid giving the shortest paths between every pair of nodes, with the start node as row and end node as column. »
Expected output:
Out[]=
+21.1Make a graph with 4 nodes in which every node is connected, displaying the resulting graph with radial drawing. »
Expected output:
Out[]=
+21.2Generate a graph in which a single node is connected to 10 others. »
Expected output:
Out[]=
+21.3Use Flatten to generate a table of the numbers 1 to 50 in which even numbers are colored red. »
Expected output:
Out[]=
+21.4Use ImageData, Flatten and Total to find the number of white pixels in Binarize[Rasterize["W"]]»
Expected output:
Out[]=
+21.5Use Flatten, IntegerDigits and Total to find the sum of all digits of all whole numbers up to 1000. »
Expected output:
Out[]=
+21.6Generate a graph with 200 connections, each between nodes with numbers randomly chosen between 0 and 100. »
Sample expected output:
Out[]=
+21.7Generate a plot that shows communities in a random graph with nodes numbered between 0 and 100, and 200 connections. »
Sample expected output:
Out[]=
What’s the difference between a “graph” and a “network”?
There’s no difference. They’re just different words for the same thing, though “graph” tends to be more common in math and other formal areas, and “network” more common in more applied areas.
What are the vertices and edges of a graph?
Vertices are the points, or nodes, of a graph. Edges are the connections. Because graphs have arisen in so many different places, there are quite a few different names used for the same thing.
How is ij understood?
It’s Rule[i, j]. Rules are used in lots of places in the Wolfram Languagesuch as giving settings for options.
How does the Wolfram Language determine how to lay out graphs?
It uses a variety of methods to try to make them as “untangled” and “balanced” as possible. One method is essentially a mechanical simulation in which each edge is like a spring that tries to get shorter, and every node “electrically repels” others. The option GraphLayout lets you specify a layout method to use.
How big a graph can the Wolfram Language handle?
It’s mostly limited by the amount of memory in your computer. Graphs with tens or hundreds of thousands of nodes are not a problem.
Can I specify annotations to nodes and edges?
Yes. You can give Graph lists of nodes and edges that include things like Annotation[node, VertexStyleRed] or Annotation[edge, EdgeWeight20]. You can extract these annotations using AnnotationValue. You can also give overall options to Graph. In addition, you can specify “tags” for edges using, for example, DirectedEdge[i, j, tag]. Tags are displayed if you use EdgeLabelsAutomatic.
Next Section