Matrix multiplication, paths, triangles & centrality

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.6%22%0Aapp%20%3D%20marimo.App(%0A%20%20%20%20width%3D%22medium%22%2C%0A%20%20%20%20app_title%3D%22Matrix%20multiplication%2C%20paths%2C%20triangles%20%26%20centrality%22%2C%0A)%0A%0A%0A%40app.cell%0Adef%20imports()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20import%20matplotlib%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20igraph%20as%20ig%0A%20%20%20%20import%20io%0A%20%20%20%20import%20random%20as%20rnd_mod%0A%0A%20%20%20%20rnd_mod.seed(1)%0A%20%20%20%20np.random.seed(1)%0A%0A%20%20%20%20matplotlib.rcParams.update(%7B%0A%20%20%20%20%20%20%20%20%22figure.facecolor%22%3A%20%22white%22%2C%0A%20%20%20%20%20%20%20%20%22axes.facecolor%22%3A%20%22white%22%2C%0A%20%20%20%20%20%20%20%20%22axes.edgecolor%22%3A%20%22%23444444%22%2C%0A%20%20%20%20%20%20%20%20%22axes.labelcolor%22%3A%20%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20%22text.color%22%3A%20%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20%22xtick.color%22%3A%20%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20%22ytick.color%22%3A%20%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20%22font.size%22%3A%2012%2C%0A%20%20%20%20%20%20%20%20%22axes.titlesize%22%3A%2013%2C%0A%20%20%20%20%20%20%20%20%22axes.labelsize%22%3A%2012%2C%0A%20%20%20%20%20%20%20%20%22figure.dpi%22%3A%20130%2C%0A%20%20%20%20%20%20%20%20%22axes.grid%22%3A%20True%2C%0A%20%20%20%20%20%20%20%20%22grid.alpha%22%3A%200.25%2C%0A%20%20%20%20%20%20%20%20%22grid.color%22%3A%20%22%23cccccc%22%2C%0A%20%20%20%20%7D)%0A%0A%20%20%20%20PALETTE%20%3D%20(%0A%20%20%20%20%20%20%20%20%22%230b789d%22%2C%20%22%23e07b00%22%2C%20%22%237a9e3b%22%2C%20%22%23b04a6f%22%2C%20%22%235e548e%22%2C%20%22%23c9a227%22%2C%0A%20%20%20%20%20%20%20%20%22%233aa6a0%22%2C%20%22%239a4f86%22%2C%20%22%23d1495b%22%2C%20%22%233a7d44%22%2C%20%22%232b6cb0%22%2C%20%22%238c6b3f%22%2C%0A%20%20%20%20)%0A%20%20%20%20ACCENT%20%3D%20%22%230b789d%22%0A%20%20%20%20NEUTRAL_NODE%20%3D%20%22%230b789d%22%0A%20%20%20%20EDGE_COLOR%20%3D%20(0.66%2C%200.66%2C%200.66%2C%200.8)%0A%0A%20%20%20%20%23%20Tighter%20cap%20than%20the%20day1%20intuition%20app%20%E2%80%94%20matrix%20displays%20do%20not%0A%20%20%20%20%23%20scale%20much%20past%20~60%20nodes.%0A%20%20%20%20MAX_NODES%20%3D%2060%0A%20%20%20%20%23%20Up%20to%20this%20size%20we%20print%20the%20actual%20numbers%20inside%20the%20matrix%20and%0A%20%20%20%20%23%20spell%20out%20the%20multiplications%20term%20by%20term.%20Florentine%20(16)%20is%20the%0A%20%20%20%20%23%20largest%20network%20that%20still%20gets%20the%20full%20numeric%20treatment.%0A%20%20%20%20NUMBER_THRESHOLD%20%3D%2016%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20ACCENT%2C%0A%20%20%20%20%20%20%20%20EDGE_COLOR%2C%0A%20%20%20%20%20%20%20%20MAX_NODES%2C%0A%20%20%20%20%20%20%20%20NUMBER_THRESHOLD%2C%0A%20%20%20%20%20%20%20%20PALETTE%2C%0A%20%20%20%20%20%20%20%20ig%2C%0A%20%20%20%20%20%20%20%20io%2C%0A%20%20%20%20%20%20%20%20mo%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20pd%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20network_catalogue(ig)%3A%0A%20%20%20%20%23%20Five%20friends%20%E2%80%94%20the%20default.%20Small%20enough%20that%20every%20entry%20of%20A%2C%0A%20%20%20%20%23%20every%20term%20of%20every%20product%2C%20and%20every%20walk%20can%20be%20read%20directly.%0A%20%20%20%20%23%20A%20triangle%20(Alice%2C%20Bob%2C%20Carol)%20plus%20a%20tail%20(Carol-David-Emma).%0A%20%20%20%20def%20_five_friends()%3A%0A%20%20%20%20%20%20%20%20g_%20%3D%20ig.Graph(%0A%20%20%20%20%20%20%20%20%20%20%20%20n%3D5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20edges%3D%5B(0%2C%201)%2C%20(0%2C%202)%2C%20(1%2C%202)%2C%20(2%2C%203)%2C%20(3%2C%204)%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20directed%3DFalse%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20g_.vs%5B%22name%22%5D%20%3D%20%5B%22Alice%22%2C%20%22Bob%22%2C%20%22Carol%22%2C%20%22David%22%2C%20%22Emma%22%5D%0A%20%20%20%20%20%20%20%20g_.vs%5B%22children%22%5D%20%3D%20%5B2%2C%200%2C%203%2C%201%2C%204%5D%0A%20%20%20%20%20%20%20%20return%20g_%0A%0A%20%20%20%20%23%20A%20small%20directed%20toy%20so%20the%20asymmetric-matrix%20story%20is%20visible.%0A%20%20%20%20def%20_toy_directed()%3A%0A%20%20%20%20%20%20%20%20g_%20%3D%20ig.Graph(%0A%20%20%20%20%20%20%20%20%20%20%20%20n%3D6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20edges%3D%5B(0%2C%201)%2C%20(0%2C%202)%2C%20(1%2C%203)%2C%20(2%2C%203)%2C%20(3%2C%204)%2C%20(4%2C%201)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(4%2C%205)%2C%20(5%2C%200)%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20directed%3DTrue%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20g_.vs%5B%22name%22%5D%20%3D%20%5B%22A%22%2C%20%22B%22%2C%20%22C%22%2C%20%22D%22%2C%20%22E%22%2C%20%22F%22%5D%0A%20%20%20%20%20%20%20%20return%20g_%0A%0A%20%20%20%20def%20_kite()%3A%0A%20%20%20%20%20%20%20%20g_%20%3D%20ig.Graph.Famous(%22Krackhardt_Kite%22)%0A%20%20%20%20%20%20%20%20g_.vs%5B%22name%22%5D%20%3D%20%5Bstr(i)%20for%20i%20in%20range(g_.vcount())%5D%0A%20%20%20%20%20%20%20%20return%20g_%0A%0A%20%20%20%20%23%20Florentine%20families%20(Padgett%201994).%0A%20%20%20%20_flor_names%20%3D%20(%0A%20%20%20%20%20%20%20%20%22ACCIAIUOL%22%2C%20%22ALBIZZI%22%2C%20%22BARBADORI%22%2C%20%22BISCHERI%22%2C%20%22CASTELLAN%22%2C%0A%20%20%20%20%20%20%20%20%22GINORI%22%2C%20%22GUADAGNI%22%2C%20%22LAMBERTES%22%2C%20%22MEDICI%22%2C%20%22PAZZI%22%2C%20%22PERUZZI%22%2C%0A%20%20%20%20%20%20%20%20%22PUCCI%22%2C%20%22RIDOLFI%22%2C%20%22SALVIATI%22%2C%20%22STROZZI%22%2C%20%22TORNABUON%22%2C%0A%20%20%20%20)%0A%20%20%20%20_flor_edges%20%3D%20(%0A%20%20%20%20%20%20%20%20(0%2C%208)%2C%20(1%2C%205)%2C%20(1%2C%206)%2C%20(1%2C%208)%2C%20(2%2C%204)%2C%20(2%2C%205)%2C%20(2%2C%208)%2C%20(2%2C%2010)%2C%0A%20%20%20%20%20%20%20%20(3%2C%206)%2C%20(3%2C%207)%2C%20(3%2C%2010)%2C%20(3%2C%2014)%2C%20(4%2C%207)%2C%20(4%2C%2010)%2C%20(4%2C%2014)%2C%0A%20%20%20%20%20%20%20%20(5%2C%208)%2C%20(6%2C%207)%2C%20(6%2C%2015)%2C%20(7%2C%2010)%2C%20(8%2C%209)%2C%20(8%2C%2012)%2C%20(8%2C%2013)%2C%0A%20%20%20%20%20%20%20%20(8%2C%2015)%2C%20(9%2C%2013)%2C%20(10%2C%2014)%2C%20(12%2C%2014)%2C%20(12%2C%2015)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20def%20_florentine()%3A%0A%20%20%20%20%20%20%20%20g_%20%3D%20ig.Graph(n%3Dlen(_flor_names)%2C%20edges%3Dlist(_flor_edges)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20directed%3DFalse)%0A%20%20%20%20%20%20%20%20g_.vs%5B%22name%22%5D%20%3D%20list(_flor_names)%0A%20%20%20%20%20%20%20%20return%20g_%0A%0A%20%20%20%20def%20_karate()%3A%0A%20%20%20%20%20%20%20%20g_%20%3D%20ig.Graph.Famous(%22Zachary%22)%0A%20%20%20%20%20%20%20%20g_.vs%5B%22name%22%5D%20%3D%20%5Bstr(i)%20for%20i%20in%20range(g_.vcount())%5D%0A%20%20%20%20%20%20%20%20return%20g_%0A%0A%20%20%20%20BUNDLED%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22Five%20friends%20(5%20nodes)%22%3A%20_five_friends%2C%0A%20%20%20%20%20%20%20%20%22Directed%20toy%20(6%20nodes)%22%3A%20_toy_directed%2C%0A%20%20%20%20%20%20%20%20%22Krackhardt%20Kite%20(10%20nodes)%22%3A%20_kite%2C%0A%20%20%20%20%20%20%20%20%22Florentine%20families%20(16%20nodes)%22%3A%20_florentine%2C%0A%20%20%20%20%20%20%20%20%22Karate%20club%20(34%20nodes)%22%3A%20_karate%2C%0A%20%20%20%20%7D%0A%20%20%20%20return%20(BUNDLED%2C)%0A%0A%0A%40app.cell%0Adef%20chooser_widgets(BUNDLED%2C%20mo)%3A%0A%20%20%20%20bundled_choice%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3Dlist(BUNDLED.keys())%2C%0A%20%20%20%20%20%20%20%20value%3D%22Five%20friends%20(5%20nodes)%22%2C%0A%20%20%20%20%20%20%20%20label%3D%22Bundled%20network%22%2C%0A%20%20%20%20)%0A%20%20%20%20file_upload%20%3D%20mo.ui.file(%0A%20%20%20%20%20%20%20%20kind%3D%22button%22%2C%0A%20%20%20%20%20%20%20%20filetypes%3D%5B%22.csv%22%2C%20%22.tsv%22%2C%20%22.txt%22%2C%20%22.graphml%22%2C%20%22.gml%22%2C%20%22.xml%22%5D%2C%0A%20%20%20%20%20%20%20%20label%3D%22Upload%20edge%20list%20or%20GraphML%2FGML%22%2C%0A%20%20%20%20%20%20%20%20multiple%3DFalse%2C%0A%20%20%20%20)%0A%20%20%20%20return%20bundled_choice%2C%20file_upload%0A%0A%0A%40app.cell%0Adef%20build_active_graph(%0A%20%20%20%20BUNDLED%2C%0A%20%20%20%20MAX_NODES%2C%0A%20%20%20%20bundled_choice%2C%0A%20%20%20%20file_upload%2C%0A%20%20%20%20ig%2C%0A%20%20%20%20io%2C%0A%20%20%20%20pd%2C%0A)%3A%0A%20%20%20%20import%20os%0A%20%20%20%20import%20tempfile%0A%0A%20%20%20%20def%20_read_uploaded(file_obj)%3A%0A%20%20%20%20%20%20%20%20name%20%3D%20file_obj.name%0A%20%20%20%20%20%20%20%20ext%20%3D%20name.lower().rsplit(%22.%22%2C%201)%5B-1%5D%20if%20%22.%22%20in%20name%20else%20%22%22%0A%20%20%20%20%20%20%20%20raw%20%3D%20file_obj.contents%0A%20%20%20%20%20%20%20%20if%20isinstance(raw%2C%20str)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20raw_bytes%20%3D%20raw.encode(%22utf-8%22)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20raw_bytes%20%3D%20raw%0A%0A%20%20%20%20%20%20%20%20if%20ext%20in%20(%22graphml%22%2C%20%22xml%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20with%20tempfile.NamedTemporaryFile(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20suffix%3D%22.graphml%22%2C%20delete%3DFalse%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20as%20tf%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tf.write(raw_bytes)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tf_path%20%3D%20tf.name%0A%20%20%20%20%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20ig.Graph.Read_GraphML(tf_path)%0A%20%20%20%20%20%20%20%20%20%20%20%20finally%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20os.unlink(tf_path)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20except%20OSError%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%0A%20%20%20%20%20%20%20%20if%20ext%20%3D%3D%20%22gml%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20with%20tempfile.NamedTemporaryFile(suffix%3D%22.gml%22%2C%20delete%3DFalse)%20as%20tf%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tf.write(raw_bytes)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tf_path%20%3D%20tf.name%0A%20%20%20%20%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20ig.Graph.Read_GML(tf_path)%0A%20%20%20%20%20%20%20%20%20%20%20%20finally%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20os.unlink(tf_path)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20except%20OSError%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%0A%20%20%20%20%20%20%20%20text%20%3D%20raw_bytes.decode(%22utf-8%22%2C%20errors%3D%22replace%22)%0A%20%20%20%20%20%20%20%20sep%20%3D%20%22%5Ct%22%20if%20text.count(%22%5Ct%22)%20%3E%20text.count(%22%2C%22)%20else%20%22%2C%22%0A%20%20%20%20%20%20%20%20df%20%3D%20pd.read_csv(io.StringIO(text)%2C%20sep%3Dsep)%0A%20%20%20%20%20%20%20%20df.columns%20%3D%20%5Bc.lower().strip()%20for%20c%20in%20df.columns%5D%0A%20%20%20%20%20%20%20%20if%20%22source%22%20not%20in%20df.columns%20or%20%22target%22%20not%20in%20df.columns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Edge%20list%20must%20have%20columns%20named%20'source'%20and%20'target'.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20edges%20%3D%20list(zip(df%5B%22source%22%5D.astype(str)%2C%20df%5B%22target%22%5D.astype(str)))%0A%20%20%20%20%20%20%20%20return%20ig.Graph.TupleList(edges%2C%20directed%3DFalse)%0A%0A%20%20%20%20upload_warning%20%3D%20None%0A%20%20%20%20source_label%20%3D%20%22%22%0A%20%20%20%20g_active%20%3D%20None%0A%0A%20%20%20%20if%20file_upload.value%20and%20len(file_upload.value)%20%3E%200%3A%0A%20%20%20%20%20%20%20%20_f%20%3D%20file_upload.value%5B0%5D%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_g%20%3D%20_read_uploaded(_f)%0A%20%20%20%20%20%20%20%20%20%20%20%20_g.simplify(multiple%3DTrue%2C%20loops%3DTrue)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_g.vcount()%20%3E%20MAX_NODES%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g%20%3D%20_g.connected_components().giant()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_g.vcount()%20%3E%20MAX_NODES%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_keep%20%3D%20sorted(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20range(_g.vcount())%2C%20key%3Dlambda%20i%3A%20-_g.degree(i)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%5B%3AMAX_NODES%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g%20%3D%20_g.subgraph(_keep)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20upload_warning%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22Upload%20had%20more%20than%20%7BMAX_NODES%7D%20nodes%3B%20trimmed%20to%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22the%20largest%20component%20(%7B_g.vcount()%7D%20nodes).%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20g_active%20%3D%20_g%0A%20%20%20%20%20%20%20%20%20%20%20%20source_label%20%3D%20f%22upload%3A%20%7B_f.name%7D%22%0A%20%20%20%20%20%20%20%20except%20Exception%20as%20_e%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20upload_warning%20%3D%20f%22Upload%20error%3A%20%7B_e%7D.%20Falling%20back%20to%20bundled.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20g_active%20%3D%20None%0A%0A%20%20%20%20if%20g_active%20is%20None%3A%0A%20%20%20%20%20%20%20%20g_active%20%3D%20BUNDLED%5Bbundled_choice.value%5D()%0A%20%20%20%20%20%20%20%20source_label%20%3D%20bundled_choice.value%0A%0A%20%20%20%20g_active.simplify(multiple%3DTrue%2C%20loops%3DTrue)%0A%20%20%20%20if%20%22name%22%20not%20in%20g_active.vs.attributes()%20or%20any(%0A%20%20%20%20%20%20%20%20v%5B%22name%22%5D%20is%20None%20for%20v%20in%20g_active.vs%0A%20%20%20%20)%3A%0A%20%20%20%20%20%20%20%20g_active.vs%5B%22name%22%5D%20%3D%20%5Bstr(i)%20for%20i%20in%20range(g_active.vcount())%5D%0A%0A%20%20%20%20g%20%3D%20g_active%0A%20%20%20%20is_directed%20%3D%20g.is_directed()%0A%20%20%20%20return%20g%2C%20is_directed%2C%20source_label%2C%20upload_warning%0A%0A%0A%40app.cell%0Adef%20sidebar_cell(%0A%20%20%20%20NUMBER_THRESHOLD%2C%0A%20%20%20%20bundled_choice%2C%0A%20%20%20%20file_upload%2C%0A%20%20%20%20g%2C%0A%20%20%20%20is_directed%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20source_label%2C%0A%20%20%20%20upload_warning%2C%0A)%3A%0A%20%20%20%20_items%20%3D%20%5B%0A%20%20%20%20%20%20%20%20mo.md(%22%23%23%23%20Active%20network%22)%2C%0A%20%20%20%20%20%20%20%20bundled_choice%2C%0A%20%20%20%20%20%20%20%20mo.md(%22_Or%20upload%20your%20own%20(CSV%20with%20%60source%60%2F%60target%60%2C%20or%20GraphML%2FGML)%3A_%22)%2C%0A%20%20%20%20%20%20%20%20file_upload%2C%0A%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22**Currently%3A**%20%20%5Cn%7Bsource_label%7D%20%20%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22_n%20%3D%20%7Bg.vcount()%7D%2C%20m%20%3D%20%7Bg.ecount()%7D%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7B'directed'%20if%20is_directed%20else%20'undirected'%7D_%22%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%5D%0A%20%20%20%20if%20upload_warning%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20_items.append(mo.md(f%22%3E%20%7Bupload_warning%7D%22))%0A%20%20%20%20_items.append(mo.md(%22---%22))%0A%20%20%20%20_items.append(mo.md(%0A%20%20%20%20%20%20%20%20%22_The%20active%20network%20drives%20every%20section%20below.%20Multiplications%20%22%0A%20%20%20%20%20%20%20%20f%22are%20spelled%20out%20with%20real%20numbers%20for%20networks%20up%20to%20%22%0A%20%20%20%20%20%20%20%20f%22%7BNUMBER_THRESHOLD%7D%20nodes%20%E2%80%94%20start%20with%20the%20tiny%20default%2C%20then%20%22%0A%20%20%20%20%20%20%20%20%22switch%20to%20a%20bigger%20one%20to%20see%20that%20nothing%20changes%20except%20%22%0A%20%20%20%20%20%20%20%20%22the%20size._%22%0A%20%20%20%20))%0A%20%20%20%20mo.sidebar(_items)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20shared_A_and_layout(g%2C%20np)%3A%0A%20%20%20%20%23%20Dense%20adjacency%20matrix.%20With%20MAX_NODES%20%3D%2060%20this%20is%20at%20most%203600%0A%20%20%20%20%23%20floats%20%E2%80%94%20cheap%20to%20recompute%20whenever%20the%20network%20changes.%0A%20%20%20%20A%20%3D%20np.array(g.get_adjacency().data%2C%20dtype%3Dfloat)%0A%0A%20%20%20%20%23%20One%20layout%20per%20active%20network%2C%20reused%20by%20every%20section%20so%20nodes%0A%20%20%20%20%23%20never%20jump%20when%20a%20slider%20moves.%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_layout%20%3D%20g.layout_kamada_kawai()%0A%20%20%20%20except%20Exception%3A%0A%20%20%20%20%20%20%20%20_layout%20%3D%20g.layout_fruchterman_reingold(niter%3D500%2C%20seed%3D1)%0A%20%20%20%20layout_coords%20%3D%20%5Btuple(row)%20for%20row%20in%20_layout.coords%5D%0A%20%20%20%20return%20A%2C%20layout_coords%0A%0A%0A%40app.cell%0Adef%20plot_helpers(EDGE_COLOR%2C%20NUMBER_THRESHOLD%2C%20ig%2C%20plt)%3A%0A%20%20%20%20def%20clean_axis(ax)%3A%0A%20%20%20%20%20%20%20%20ax.set_facecolor(%22white%22)%0A%20%20%20%20%20%20%20%20ax.grid(False)%0A%20%20%20%20%20%20%20%20ax.set_xticks(%5B%5D)%0A%20%20%20%20%20%20%20%20ax.set_yticks(%5B%5D)%0A%20%20%20%20%20%20%20%20for%20side%20in%20(%22top%22%2C%20%22right%22%2C%20%22bottom%22%2C%20%22left%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.spines%5Bside%5D.set_visible(False)%0A%0A%20%20%20%20def%20draw_graph(ax%2C%20g_%2C%20coords%2C%20vertex_color%3D%22%230b789d%22%2C%20vertex_size%3DNone%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20labels%3DNone%2C%20edge_color%3DNone%2C%20edge_width%3D1.2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label_size%3D12)%3A%0A%20%20%20%20%20%20%20%20clean_axis(ax)%0A%20%20%20%20%20%20%20%20n_%20%3D%20g_.vcount()%0A%20%20%20%20%20%20%20%20if%20vertex_size%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20vertex_size%20%3D%2030%20if%20n_%20%3C%3D%2016%20else%20(18%20if%20n_%20%3C%3D%2034%20else%2010)%0A%20%20%20%20%20%20%20%20if%20labels%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20labels%20%3D%20g_.vs%5B%22name%22%5D%20if%20n_%20%3C%3D%2030%20else%20%5B%22%22%5D%20*%20n_%0A%20%20%20%20%20%20%20%20ig.plot(%0A%20%20%20%20%20%20%20%20%20%20%20%20g_%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20target%3Dax%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20layout%3Dcoords%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20vertex_color%3Dvertex_color%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20vertex_size%3Dvertex_size%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20vertex_frame_width%3D0%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20vertex_label%3Dlabels%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20vertex_label_size%3Dlabel_size%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20vertex_label_color%3D%22%23222222%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20edge_color%3Dedge_color%20if%20edge_color%20is%20not%20None%20else%20EDGE_COLOR%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20edge_width%3Dedge_width%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20edge_arrow_size%3D0.8%20if%20g_.is_directed()%20else%200.0%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20def%20matrix_with_numbers(ax%2C%20M%2C%20names_%2C%20highlight_row%3DNone%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20highlight_cell%3DNone%2C%20cmap%3D%22Blues%22%2C%20title%3DNone)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Heatmap%20of%20M%3B%20prints%20the%20integers%20in%20the%20cells%20for%20small%20n.%22%22%22%0A%20%20%20%20%20%20%20%20n_%20%3D%20M.shape%5B0%5D%0A%20%20%20%20%20%20%20%20vmax%20%3D%20max(1.0%2C%20float(M.max()))%0A%20%20%20%20%20%20%20%20cm%20%3D%20plt.get_cmap(cmap)%0A%20%20%20%20%20%20%20%20ax.imshow(M%2C%20cmap%3Dcmap%2C%20vmin%3D0%2C%20vmax%3Dvmax%2C%20aspect%3D%22equal%22)%0A%20%20%20%20%20%20%20%20ax.grid(False)%0A%20%20%20%20%20%20%20%20if%20n_%20%3C%3D%2030%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_xticks(range(n_))%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_yticks(range(n_))%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_xticklabels(names_%2C%20rotation%3D90%2C%20fontsize%3D9)%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_yticklabels(names_%2C%20fontsize%3D9)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_xticks(%5B%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_yticks(%5B%5D)%0A%20%20%20%20%20%20%20%20if%20n_%20%3C%3D%20NUMBER_THRESHOLD%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20fs%20%3D%2012%20if%20n_%20%3C%3D%208%20else%209%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20ri%20in%20range(n_)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20ci%20in%20range(n_)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20v%20%3D%20M%5Bri%2C%20ci%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20red%2C%20grn%2C%20blu%2C%20_%20%3D%20cm(v%20%2F%20vmax)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lum%20%3D%200.299%20*%20red%20%2B%200.587%20*%20grn%20%2B%200.114%20*%20blu%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20v%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20col%20%3D%20%22%23bbbbbb%22%20if%20lum%20%3E%200.5%20else%20%22%23888888%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20col%20%3D%20%22white%22%20if%20lum%20%3C%200.5%20else%20%22%23333333%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.text(ci%2C%20ri%2C%20f%22%7Bint(v)%7D%22%2C%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3Dfs%2C%20color%3Dcol)%0A%20%20%20%20%20%20%20%20if%20highlight_row%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.add_patch(plt.Rectangle(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(-0.5%2C%20highlight_row%20-%200.5)%2C%20n_%2C%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fill%3DFalse%2C%20edgecolor%3D%22%23c0223b%22%2C%20linewidth%3D2.0%2C%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%20%20%20%20%20%20%20%20if%20highlight_cell%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20hri%2C%20hci%20%3D%20highlight_cell%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.add_patch(plt.Rectangle(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(hci%20-%200.5%2C%20hri%20-%200.5)%2C%201%2C%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fill%3DFalse%2C%20edgecolor%3D%22%231ed8a3%22%2C%20linewidth%3D2.5%2C%20zorder%3D6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%20%20%20%20%20%20%20%20if%20title%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_title(title)%0A%0A%20%20%20%20def%20draw_block(ax%2C%20M%2C%20x0%2C%20names_%2C%20fs%2C%20row_names%3DFalse%2C%20col_names%3DFalse%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20hl_row%3DNone%2C%20hl_col%3DNone%2C%20hl_cell%3DNone%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20hl_row_color%3D%22%23c0223b%22%2C%20hl_col_color%3D%22%230b789d%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20hl_cell_color%3D%22%231ed8a3%22)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Draw%20matrix%20M%20as%20a%20numeric%20grid%20starting%20at%20x%20%3D%20x0.%0A%0A%20%20%20%20%20%20%20%20Row%200%20is%20at%20the%20top%20(caller%20must%20invert%20the%20y%20axis).%20Returns%20the%0A%20%20%20%20%20%20%20%20x%20coordinate%20of%20the%20right%20edge%20of%20the%20block.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20nr%2C%20nc%20%3D%20M.shape%0A%20%20%20%20%20%20%20%20for%20r%20in%20range(nr%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.plot(%5Bx0%2C%20x0%20%2B%20nc%5D%2C%20%5Br%2C%20r%5D%2C%20color%3D%22%23cccccc%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidth%3D0.6%2C%20zorder%3D1)%0A%20%20%20%20%20%20%20%20for%20c%20in%20range(nc%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.plot(%5Bx0%20%2B%20c%2C%20x0%20%2B%20c%5D%2C%20%5B0%2C%20nr%5D%2C%20color%3D%22%23cccccc%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidth%3D0.6%2C%20zorder%3D1)%0A%20%20%20%20%20%20%20%20if%20hl_row%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.add_patch(plt.Rectangle(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(x0%2C%20hl_row)%2C%20nc%2C%201%2C%20facecolor%3Dhl_row_color%2C%20alpha%3D0.12%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3Dhl_row_color%2C%20linewidth%3D1.8%2C%20zorder%3D2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%20%20%20%20%20%20%20%20if%20hl_col%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.add_patch(plt.Rectangle(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(x0%20%2B%20hl_col%2C%200)%2C%201%2C%20nr%2C%20facecolor%3Dhl_col_color%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20alpha%3D0.12%2C%20edgecolor%3Dhl_col_color%2C%20linewidth%3D1.8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%20%20%20%20%20%20%20%20if%20hl_cell%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20cr%2C%20cc%20%3D%20hl_cell%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.add_patch(plt.Rectangle(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(x0%20%2B%20cc%2C%20cr)%2C%201%2C%201%2C%20fill%3DFalse%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3Dhl_cell_color%2C%20linewidth%3D2.5%2C%20zorder%3D4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%20%20%20%20%20%20%20%20for%20r%20in%20range(nr)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20c%20in%20range(nc)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20v%20%3D%20M%5Br%2C%20c%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.text(x0%20%2B%20c%20%2B%200.5%2C%20r%20%2B%200.5%2C%20f%22%7Bv%3Ag%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20fontsize%3Dfs%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23aaaaaa%22%20if%20v%20%3D%3D%200%20else%20%22%23222222%22%2C%20zorder%3D3)%0A%20%20%20%20%20%20%20%20if%20row_names%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20r%20in%20range(nr)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.text(x0%20-%200.3%2C%20r%20%2B%200.5%2C%20names_%5Br%5D%2C%20ha%3D%22right%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22center%22%2C%20fontsize%3Dfs%2C%20color%3D%22%23333333%22)%0A%20%20%20%20%20%20%20%20if%20col_names%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20c%20in%20range(nc)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.text(x0%20%2B%20c%20%2B%200.5%2C%20-0.3%2C%20names_%5Bc%5D%2C%20ha%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22bottom%22%2C%20rotation%3D90%2C%20fontsize%3Dfs%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23333333%22)%0A%20%20%20%20%20%20%20%20return%20x0%20%2B%20nc%0A%0A%20%20%20%20def%20enumerate_walks(A_%2C%20start%2C%20end%2C%20k%2C%20cap%3D200)%3A%0A%20%20%20%20%20%20%20%20%22%22%22All%20walks%20of%20length%20k%20from%20start%20to%20end%20(node%20index%20lists).%22%22%22%0A%20%20%20%20%20%20%20%20n_%20%3D%20A_.shape%5B0%5D%0A%20%20%20%20%20%20%20%20out%20%3D%20%5B%5D%0A%0A%20%20%20%20%20%20%20%20def%20dfs(path)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(out)%20%3E%3D%20cap%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(path)%20%3D%3D%20k%20%2B%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20path%5B-1%5D%20%3D%3D%20end%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20out.append(list(path))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20nxt%20in%20range(n_)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20A_%5Bpath%5B-1%5D%2C%20nxt%5D%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20path.append(nxt)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dfs(path)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20path.pop()%0A%0A%20%20%20%20%20%20%20%20dfs(%5Bstart%5D)%0A%20%20%20%20%20%20%20%20return%20out%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20clean_axis%2C%0A%20%20%20%20%20%20%20%20draw_block%2C%0A%20%20%20%20%20%20%20%20draw_graph%2C%0A%20%20%20%20%20%20%20%20enumerate_walks%2C%0A%20%20%20%20%20%20%20%20matrix_with_numbers%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20title(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Matrix%20multiplication%20is%20counting%20paths%0A%0A%20%20%20%20*Javier%20Garcia-Bernardo%20%E2%80%94%20ODISSEI%20Social%20Data%20Science%20team%20(SoDa)%20%26%20Department%20of%20Methodology%20and%20Statistics%2C%20Utrecht%20University*%0A%0A%20%20%20%20A%20network%20can%20be%20written%20as%20a%20matrix%20%24A%24%3A%20one%20row%20and%20one%20column%20per%0A%20%20%20%20node%2C%20with%20%24A_%7Bij%7D%20%3D%201%24%20when%20%24i%24%20and%20%24j%24%20are%20connected.%20That%20is%20just%0A%20%20%20%20storage.%20The%20magic%20starts%20when%20you%20**multiply**%3A%0A%0A%20%20%20%20-%20%60A%20%40%20x%60%20asks%20every%20node%20a%20question%20about%20its%20**neighbours**%20(1%20step).%0A%20%20%20%20-%20%60A%20%40%20A%60%20counts%20**walks%20of%20length%202**%20%E2%80%94%20friends%20of%20friends.%0A%20%20%20%20-%20The%20diagonal%20of%20%60A%20%40%20A%20%40%20A%60%20counts%20**triangles**.%0A%20%20%20%20-%20Multiplying%20again%20and%20again%20makes%20a%20notion%20of%20**importance**%20emerge.%0A%0A%20%20%20%20The%20same%20trick%20%E2%80%94%20follow%20the%20paths%2C%20add%20them%20up%20%E2%80%94%20is%20behind%20search%0A%20%20%20%20ranking%2C%20epidemic%20models%2C%20recommendation%20systems%2C%20and%20community%0A%20%20%20%20detection.%20Learn%20to%20read%20one%20multiplication%20and%20you%20can%20read%20them%20all.%0A%0A%20%20%20%20The%20default%20network%20is%20five%20people%2C%20so%20every%20number%20in%20every%0A%20%20%20%20multiplication%20is%20visible.%20Nothing%20is%20hidden%20inside%20the%20math%3A%20you%20can%0A%20%20%20%20check%20each%20product%20with%20your%20finger%20on%20the%20picture.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20section1_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%201.%20The%20network%20and%20its%20matrix%0A%0A%20%20%20%20The%20picture%20and%20the%20matrix%20carry%20exactly%20the%20same%20information.%0A%20%20%20%20**Row%20%24i%24%20answers%20one%20question%3A%20who%20is%20%24i%24%20connected%20to%3F**%20A%201%20in%0A%20%20%20%20column%20%24j%24%20means%20%22yes%2C%20%24j%24%22.%20The%20diagonal%20is%20all%20zeros%20(nobody%20is%0A%20%20%20%20their%20own%20neighbour)%2C%20and%20for%20an%20undirected%20network%20the%20matrix%20is%0A%20%20%20%20symmetric%3A%20if%20Alice%20knows%20Bob%2C%20Bob%20knows%20Alice.%0A%0A%20%20%20%20Pick%20a%20node%20and%20find%20its%20row.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s1_widgets(g%2C%20mo)%3A%0A%20%20%20%20row_node%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3Dlist(g.vs%5B%22name%22%5D)%2C%0A%20%20%20%20%20%20%20%20value%3Dg.vs%5B%22name%22%5D%5B0%5D%2C%0A%20%20%20%20%20%20%20%20label%3D%22Pick%20a%20node%22%2C%0A%20%20%20%20)%0A%20%20%20%20row_node%0A%20%20%20%20return%20(row_node%2C)%0A%0A%0A%40app.cell%0Adef%20s1_plot(%0A%20%20%20%20A%2C%0A%20%20%20%20ACCENT%2C%0A%20%20%20%20EDGE_COLOR%2C%0A%20%20%20%20draw_graph%2C%0A%20%20%20%20g%2C%0A%20%20%20%20layout_coords%2C%0A%20%20%20%20matrix_with_numbers%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20row_node%2C%0A)%3A%0A%20%20%20%20_n%20%3D%20g.vcount()%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20_f%20%3D%20_names.index(row_node.value)%0A%0A%20%20%20%20_fig%2C%20(_axL%2C%20_axR)%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3D(11%2C%205.2))%0A%0A%20%20%20%20%23%20Left%3A%20graph%20with%20the%20chosen%20node%20and%20its%20edges%20highlighted.%0A%20%20%20%20_ecols%20%3D%20%5B%5D%0A%20%20%20%20_ewids%20%3D%20%5B%5D%0A%20%20%20%20for%20_e%20in%20g.es%3A%0A%20%20%20%20%20%20%20%20if%20_f%20in%20(_e.source%2C%20_e.target)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ecols.append(ACCENT)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ewids.append(3.0)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ecols.append(EDGE_COLOR)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ewids.append(1.2)%0A%20%20%20%20_vcols%20%3D%20%5B%22%23c8dde6%22%5D%20*%20_n%0A%20%20%20%20_vcols%5B_f%5D%20%3D%20ACCENT%0A%20%20%20%20draw_graph(_axL%2C%20g%2C%20layout_coords%2C%20vertex_color%3D_vcols%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edge_color%3D_ecols%2C%20edge_width%3D_ewids)%0A%20%20%20%20_axL.set_title(f%22%7Brow_node.value%7D%20and%20its%20edges%22)%0A%0A%20%20%20%20%23%20Right%3A%20the%20matrix%20with%20that%20row%20boxed.%0A%20%20%20%20matrix_with_numbers(_axR%2C%20A%2C%20_names%2C%20highlight_row%3D_f%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20title%3D%22Adjacency%20matrix%20A%22)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20_row%20%3D%20A%5B_f%5D%0A%20%20%20%20_nbrs%20%3D%20%5B_names%5B_j%5D%20for%20_j%20in%20range(_n)%20if%20_row%5B_j%5D%20%3E%200%5D%0A%20%20%20%20_sym%20%3D%20bool(np.array_equal(A%2C%20A.T))%0A%20%20%20%20_read%20%3D%20(%0A%20%20%20%20%20%20%20%20f%22**Row%20%7Brow_node.value%7D**%20%3D%20%22%0A%20%20%20%20%20%20%20%20f%22%5B%7B'%2C%20'.join(str(int(_v))%20for%20_v%20in%20_row)%7D%5D%22%0A%20%20%20%20%20%20%20%20if%20_n%20%3C%3D%2016%20else%20f%22**Row%20%7Brow_node.value%7D**%22%0A%20%20%20%20)%0A%20%20%20%20_msg%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20f%22%7B_read%7D%20%E2%80%94%20connected%20to%20%22%0A%20%20%20%20%20%20%20%20f%22%7B'%2C%20'.join('**'%20%2B%20_b%20%2B%20'**'%20for%20_b%20in%20_nbrs)%20if%20_nbrs%20else%20'nobody'%7D.%22%0A%20%20%20%20%20%20%20%20f%22%20The%20row%20sum%20is%20%7Bint(_row.sum())%7D%3A%20that%20is%20the%20**degree**%22%0A%20%20%20%20%20%20%20%20f%22%7B'%20(out-degree%2C%20since%20this%20network%20is%20directed)'%20if%20g.is_directed()%20else%20''%7D.%22%0A%20%20%20%20%20%20%20%20f%22%20This%20matrix%20is%20%7B'symmetric%20%E2%80%94%20undirected'%20if%20_sym%20else%20'NOT%20symmetric%20%E2%80%94%20directed%3A%20row%20%3D%20who%20I%20point%20to%2C%20column%20%3D%20who%20points%20to%20me'%7D.%22%0A%20%20%20%20%20%20%20%20f%22%20Trace%20(sum%20of%20the%20diagonal)%20%3D%20%7Bint(np.trace(A))%7D.%22%0A%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_fig%2C%20_msg%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20section2_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%202.%20%60A%20%40%20x%60%20%E2%80%94%20ask%20every%20node%20about%20its%20neighbours%0A%0A%20%20%20%20Multiply%20%24A%24%20by%20a%20vector%20%24x%24%20(one%20value%20per%20node)%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20y%20%3D%20A%5C%2Cx%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Entry%20%24i%24%20of%20the%20result%20is%20**row%20%24i%24%20of%20%24A%24%20times%20the%20vector%20%24x%24**%3A%0A%20%20%20%20the%201s%20in%20the%20row%20keep%20exactly%20the%20neighbours'%20values%2C%20the%200s%20erase%0A%20%20%20%20everyone%20else.%20So%20%24y_i%24%20is%20the%20total%20of%20%24x%24%20over%20%24i%24's%20neighbours%20%E2%80%94%0A%20%20%20%20no%20loops%2C%20no%20code%2C%20one%20multiplication.%0A%0A%20%20%20%20Try%20it%20with%20the%20number%20of%20children%20each%20person%20has%3A%20%24y%24%20answers%0A%20%20%20%20%22how%20many%20children%20do%20my%20friends%20have%2C%20in%20total%3F%22%20for%20everybody%20at%0A%20%20%20%20once.%20With%20%24x%24%20%3D%20all%20ones%2C%20each%20neighbour%20contributes%201%2C%20so%20%24y%24%20is%0A%20%20%20%20the%20degree.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s2_widgets(g%2C%20mo)%3A%0A%20%20%20%20_opts%20%3D%20%5B%5D%0A%20%20%20%20if%20%22children%22%20in%20g.vs.attributes()%3A%0A%20%20%20%20%20%20%20%20_opts.append(%22Number%20of%20children%20(attribute)%22)%0A%20%20%20%20_opts.append(%22All%20ones%20(counts%20neighbours%20%3D%20degree)%22)%0A%20%20%20%20_opts.append(%22Example%20attribute%20(random%200-5)%22)%0A%20%20%20%20x_kind%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3D_opts%2C%20value%3D_opts%5B0%5D%2C%20label%3D%22Vector%20x%22%2C%0A%20%20%20%20)%0A%20%20%20%20focus_node%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3Dlist(g.vs%5B%22name%22%5D)%2C%0A%20%20%20%20%20%20%20%20value%3Dg.vs%5B%22name%22%5D%5B0%5D%2C%0A%20%20%20%20%20%20%20%20label%3D%22Spell%20out%20the%20multiplication%20for%22%2C%0A%20%20%20%20)%0A%20%20%20%20mo.hstack(%5Bx_kind%2C%20focus_node%5D%2C%20gap%3D1.0%2C%20widths%3D%22equal%22)%0A%20%20%20%20return%20focus_node%2C%20x_kind%0A%0A%0A%40app.cell%0Adef%20s2_plot(%0A%20%20%20%20A%2C%0A%20%20%20%20ACCENT%2C%0A%20%20%20%20EDGE_COLOR%2C%0A%20%20%20%20NUMBER_THRESHOLD%2C%0A%20%20%20%20clean_axis%2C%0A%20%20%20%20draw_block%2C%0A%20%20%20%20draw_graph%2C%0A%20%20%20%20focus_node%2C%0A%20%20%20%20g%2C%0A%20%20%20%20layout_coords%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20x_kind%2C%0A)%3A%0A%20%20%20%20_n%20%3D%20g.vcount()%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20_f%20%3D%20_names.index(focus_node.value)%0A%0A%20%20%20%20if%20x_kind.value%20%3D%3D%20%22Number%20of%20children%20(attribute)%22%3A%0A%20%20%20%20%20%20%20%20_x%20%3D%20np.array(g.vs%5B%22children%22%5D%2C%20dtype%3Dfloat)%0A%20%20%20%20%20%20%20%20_xlabel%20%3D%20%22x%20%3D%20number%20of%20children%22%0A%20%20%20%20elif%20x_kind.value%20%3D%3D%20%22All%20ones%20(counts%20neighbours%20%3D%20degree)%22%3A%0A%20%20%20%20%20%20%20%20_x%20%3D%20np.ones(_n)%0A%20%20%20%20%20%20%20%20_xlabel%20%3D%20%22x%20%3D%20all%20ones%22%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_rng%20%3D%20np.random.default_rng(7)%0A%20%20%20%20%20%20%20%20_x%20%3D%20_rng.integers(0%2C%206%2C%20_n).astype(float)%0A%20%20%20%20%20%20%20%20_xlabel%20%3D%20%22x%20%3D%20example%20attribute%20(random%200-5)%22%0A%0A%20%20%20%20_y%20%3D%20A%20%40%20_x%0A%0A%20%20%20%20%23%20Figure%201%3A%20graph%20(x%20values%20on%20the%20nodes)%20%2B%20bar%20charts%20of%20x%20and%20y.%0A%20%20%20%20_fig1%20%3D%20plt.figure(figsize%3D(11.5%2C%205.2))%0A%20%20%20%20_gs%20%3D%20_fig1.add_gridspec(2%2C%202%2C%20width_ratios%3D%5B1.5%2C%201.0%5D)%0A%20%20%20%20_axG%20%3D%20_fig1.add_subplot(_gs%5B%3A%2C%200%5D)%0A%20%20%20%20_axX%20%3D%20_fig1.add_subplot(_gs%5B0%2C%201%5D)%0A%20%20%20%20_axY%20%3D%20_fig1.add_subplot(_gs%5B1%2C%201%5D)%0A%0A%20%20%20%20_ecols%20%3D%20%5B%5D%0A%20%20%20%20_ewids%20%3D%20%5B%5D%0A%20%20%20%20for%20_e%20in%20g.es%3A%0A%20%20%20%20%20%20%20%20if%20_f%20in%20(_e.source%2C%20_e.target)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ecols.append(ACCENT)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ewids.append(3.0)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ecols.append(EDGE_COLOR)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ewids.append(1.2)%0A%20%20%20%20_vcols%20%3D%20%5B%22%23c8dde6%22%5D%20*%20_n%0A%20%20%20%20_vcols%5B_f%5D%20%3D%20ACCENT%0A%20%20%20%20if%20_n%20%3C%3D%20NUMBER_THRESHOLD%3A%0A%20%20%20%20%20%20%20%20_labels%20%3D%20%5Bf%22%7B_names%5B_i%5D%7D%5Cnx%3D%7B_x%5B_i%5D%3Ag%7D%22%20for%20_i%20in%20range(_n)%5D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_labels%20%3D%20None%0A%20%20%20%20draw_graph(_axG%2C%20g%2C%20layout_coords%2C%20vertex_color%3D_vcols%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edge_color%3D_ecols%2C%20edge_width%3D_ewids%2C%20labels%3D_labels%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label_size%3D11)%0A%20%20%20%20_axG.set_title(f%22Each%20node%20carries%20its%20x%20value%20%20(%7B_xlabel%7D)%22)%0A%0A%20%20%20%20_show_ticks%20%3D%20_n%20%3C%3D%2016%0A%20%20%20%20_axX.bar(range(_n)%2C%20_x%2C%20color%3D%22%23888888%22%2C%20edgecolor%3D%22white%22)%0A%20%20%20%20_axX.set_title(%22Input%20%20x%22)%0A%20%20%20%20_axY.bar(range(_n)%2C%20_y%2C%20color%3DACCENT%2C%20edgecolor%3D%22white%22)%0A%20%20%20%20_axY.set_title(%22Output%20%20y%20%3D%20A%20%40%20x%22)%0A%20%20%20%20for%20_ax%20in%20(_axX%2C%20_axY)%3A%0A%20%20%20%20%20%20%20%20if%20_show_ticks%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.set_xticks(range(_n))%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.set_xticklabels(_names%2C%20rotation%3D90%2C%20fontsize%3D9)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20%20%20%20%20_ax.spines%5B%22top%22%5D.set_visible(False)%0A%20%20%20%20%20%20%20%20_ax.spines%5B%22right%22%5D.set_visible(False)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20%23%20Figure%202%3A%20the%20multiplication%20itself%20%E2%80%94%20A%20(row%20highlighted)%20%40%20x%20%3D%20y.%0A%20%20%20%20if%20_n%20%3C%3D%20NUMBER_THRESHOLD%3A%0A%20%20%20%20%20%20%20%20_fs%20%3D%2012%20if%20_n%20%3C%3D%206%20else%20(10%20if%20_n%20%3C%3D%2010%20else%207.5)%0A%20%20%20%20%20%20%20%20_maxlen%20%3D%20max(len(_nm)%20for%20_nm%20in%20_names)%0A%20%20%20%20%20%20%20%20_left_margin%20%3D%200.35%20%2B%200.21%20*%20_maxlen%20*%20_fs%20%2F%209.0%0A%20%20%20%20%20%20%20%20_top_margin%20%3D%200.6%20%2B%200.21%20*%20_maxlen%20*%20_fs%20%2F%209.0%0A%20%20%20%20%20%20%20%20_gap%20%3D%201.7%0A%0A%20%20%20%20%20%20%20%20_figW%20%3D%2011.5%0A%20%20%20%20%20%20%20%20_x_total%20%3D%20_left_margin%20%2B%20_n%20%2B%20_gap%20%2B%201%20%2B%20_gap%20%2B%201%20%2B%201.8%0A%20%20%20%20%20%20%20%20_y_total%20%3D%20_n%20%2B%202.6%20%2B%20_top_margin%0A%20%20%20%20%20%20%20%20_figH%20%3D%20min(9.0%2C%20max(3.4%2C%20_figW%20*%20_y_total%20%2F%20_x_total))%0A%20%20%20%20%20%20%20%20_fig2%2C%20_axM%20%3D%20plt.subplots(figsize%3D(_figW%2C%20_figH))%0A%20%20%20%20%20%20%20%20clean_axis(_axM)%0A%20%20%20%20%20%20%20%20_axM.set_aspect(%22equal%22)%0A%0A%20%20%20%20%20%20%20%20_xe%20%3D%20draw_block(_axM%2C%20A%2C%200%2C%20_names%2C%20_fs%2C%20row_names%3DTrue%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20col_names%3DTrue%2C%20hl_row%3D_f)%0A%20%20%20%20%20%20%20%20_axM.text(_xe%20%2B%20_gap%20%2F%202%2C%20_n%20%2F%202%2C%20%22%40%22%2C%20fontsize%3D15%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20color%3D%22%23333333%22)%0A%20%20%20%20%20%20%20%20_xv%20%3D%20_xe%20%2B%20_gap%0A%20%20%20%20%20%20%20%20draw_block(_axM%2C%20_x.reshape(-1%2C%201)%2C%20_xv%2C%20_names%2C%20_fs%2C%20hl_col%3D0)%0A%20%20%20%20%20%20%20%20_axM.text(_xv%20%2B%201%20%2B%20_gap%20%2F%202%2C%20_n%20%2F%202%2C%20%22%3D%22%2C%20fontsize%3D15%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20color%3D%22%23333333%22)%0A%20%20%20%20%20%20%20%20_xy%20%3D%20_xv%20%2B%201%20%2B%20_gap%0A%20%20%20%20%20%20%20%20draw_block(_axM%2C%20_y.reshape(-1%2C%201)%2C%20_xy%2C%20_names%2C%20_fs%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20hl_cell%3D(_f%2C%200))%0A%0A%20%20%20%20%20%20%20%20%23%20The%20products%2C%20written%20under%20the%20column%20they%20come%20from.%0A%20%20%20%20%20%20%20%20for%20_m%20in%20range(_n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_zero%20%3D%20A%5B_f%2C%20_m%5D%20%3D%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20_axM.text(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_m%20%2B%200.5%2C%20_n%20%2B%200.85%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7BA%5B_f%2C%20_m%5D%3Ag%7D*%7B_x%5B_m%5D%3Ag%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20fontsize%3D_fs%20*%200.92%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23bbbbbb%22%20if%20_zero%20else%20%22%23c0223b%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_m%20%3C%20_n%20-%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_axM.text(_m%20%2B%201.0%2C%20_n%20%2B%200.85%2C%20%22%2B%22%2C%20ha%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22center%22%2C%20fontsize%3D_fs%20*%200.92%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23bbbbbb%22)%0A%20%20%20%20%20%20%20%20_axM.text(_xy%20%2B%200.5%2C%20_n%20%2B%200.85%2C%20f%22%3D%20%7B_y%5B_f%5D%3Ag%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20fontsize%3D_fs%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontweight%3D%22bold%22%2C%20color%3D%22%23c0223b%22)%0A%20%20%20%20%20%20%20%20_axM.text(%0A%20%20%20%20%20%20%20%20%20%20%20%200%2C%20_n%20%2B%201.9%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22y(%7Bfocus_node.value%7D)%20%20%3D%20%20row%20%7Bfocus_node.value%7D%20of%20A%20%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22times%20%20x%20%20%20(red%20row%2C%20blue%20vector)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22left%22%2C%20va%3D%22center%22%2C%20fontsize%3D_fs%2C%20color%3D%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_axM.set_xlim(-_left_margin%2C%20_xy%20%2B%201.9)%0A%20%20%20%20%20%20%20%20_axM.set_ylim(_n%20%2B%202.6%2C%20-_top_margin)%0A%20%20%20%20%20%20%20%20_body%20%3D%20mo.vstack(%5B_fig1%2C%20_fig2%5D)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_body%20%3D%20mo.vstack(%5B_fig1%2C%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22_Switch%20to%20a%20network%20with%20at%20most%20%7BNUMBER_THRESHOLD%7D%20nodes%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22to%20see%20the%20multiplication%20spelled%20out%20%E2%80%94%20the%20math%20is%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22identical._%22%0A%20%20%20%20%20%20%20%20)%5D)%0A%0A%20%20%20%20if%20x_kind.value%20%3D%3D%20%22All%20ones%20(counts%20neighbours%20%3D%20degree)%22%3A%0A%20%20%20%20%20%20%20%20_note%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22With%20%24x%24%20%3D%20all%20ones%20every%20neighbour%20contributes%20exactly%201%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22so%20%60A%20%40%20x%60%20%3D%20number%20of%20neighbours%20%3D%20**degree**.%20One%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22multiplication%20computed%20the%20degree%20of%20every%20node%20at%20once.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_nbrs%20%3D%20%5B_names%5B_j%5D%20for%20_j%20in%20range(_n)%20if%20A%5B_f%2C%20_j%5D%20%3E%200%5D%0A%20%20%20%20%20%20%20%20_note%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22Check%20it%20on%20the%20picture%3A%20%7Bfocus_node.value%7D's%20neighbours%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22are%20%7B'%2C%20'.join(_nbrs)%20if%20_nbrs%20else%20'nobody'%7D%3B%20add%20their%20x%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22values%20and%20you%20get%20%7B_y%5B_f%5D%3Ag%7D.%20The%20matrix%20did%20this%20for%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22every%20node%20simultaneously%20%E2%80%94%20that%20is%20all%20matrix%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22multiplication%20is.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_body%2C%20mo.md(_note)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20section3_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%203.%20Average%20of%20friends%2C%20and%20the%20friendship%20paradox%0A%0A%20%20%20%20Divide%20the%20total%20by%20the%20number%20of%20neighbours%20(the%20degree)%20and%20you%0A%20%20%20%20get%20an%20**average%20over%20friends**%3A%20%60(A%20%40%20x)%20%2F%20k%60%2C%20elementwise.%0A%0A%20%20%20%20Now%20feed%20the%20machine%20its%20own%20degrees%3A%20take%20%24x%20%3D%20k%24.%20Then%20each%20entry%0A%20%20%20%20is%20%22the%20average%20degree%20of%20my%20friends%22.%20Comparing%20it%20with%20your%20own%0A%20%20%20%20degree%20gives%20a%20famous%20surprise%20%E2%80%94%20**on%20average%2C%20your%20friends%20have%0A%20%20%20%20more%20friends%20than%20you**.%20Popular%20people%20show%20up%20in%20many%20friend%0A%20%20%20%20lists%2C%20so%20they%20drag%20every%20list's%20average%20up.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s3_plot(A%2C%20ACCENT%2C%20draw_graph%2C%20g%2C%20layout_coords%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_n%20%3D%20g.vcount()%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20_deg%20%3D%20A.sum(axis%3D1)%0A%20%20%20%20_safe%20%3D%20np.where(_deg%20%3E%200%2C%20_deg%2C%201.0)%0A%20%20%20%20_avg_nbr%20%3D%20(A%20%40%20_deg)%20%2F%20_safe%0A%20%20%20%20_avg_nbr%5B_deg%20%3D%3D%200%5D%20%3D%20np.nan%0A%0A%20%20%20%20_valid%20%3D%20~np.isnan(_avg_nbr)%0A%20%20%20%20_mean_self%20%3D%20float(_deg%5B_valid%5D.mean())%20if%20_valid.any()%20else%200.0%0A%20%20%20%20_mean_nbr%20%3D%20float(np.nanmean(_avg_nbr))%20if%20_valid.any()%20else%200.0%0A%0A%20%20%20%20%23%20The%20network%2C%20with%20each%20node%20labelled%20by%20its%20degree.%0A%20%20%20%20_figG%2C%20_axG%20%3D%20plt.subplots(figsize%3D(6.0%2C%205.2))%0A%20%20%20%20if%20_deg.max()%20%3E%200%3A%0A%20%20%20%20%20%20%20%20_sizes%20%3D%20list(20%20%2B%2022%20*%20(_deg%20%2F%20_deg.max()))%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_sizes%20%3D%20None%0A%20%20%20%20if%20_n%20%3C%3D%2016%3A%0A%20%20%20%20%20%20%20%20_labels%20%3D%20%5Bf%22%7B_names%5B_i%5D%7D%5Cnk%3D%7Bint(_deg%5B_i%5D)%7D%22%20for%20_i%20in%20range(_n)%5D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_labels%20%3D%20%5B%22%22%5D%20*%20_n%0A%20%20%20%20draw_graph(_axG%2C%20g%2C%20layout_coords%2C%20vertex_color%3DACCENT%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20vertex_size%3D_sizes%2C%20labels%3D_labels%2C%20label_size%3D11)%0A%20%20%20%20_axG.set_title(%22Node%20size%20%3D%20degree%22)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20if%20_n%20%3C%3D%2012%3A%0A%20%20%20%20%20%20%20%20%23%20Numbers-first%3A%20a%20table%20you%20can%20check%20by%20hand.%0A%20%20%20%20%20%20%20%20_rows%20%3D%20%5B%22%7C%20Node%20%7C%20Own%20degree%20%7C%20Friends%20(their%20degrees)%20%7C%20Friends'%20average%20%7C%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%7C---%7C---%7C---%7C---%7C%22%5D%0A%20%20%20%20%20%20%20%20for%20_i%20in%20range(_n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_nbrs%20%3D%20%5B_j%20for%20_j%20in%20range(_n)%20if%20A%5B_i%2C%20_j%5D%20%3E%200%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_flist%20%3D%20%22%2C%20%22.join(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7B_names%5B_j%5D%7D%20(%7Bint(_deg%5B_j%5D)%7D)%22%20for%20_j%20in%20_nbrs%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20if%20_nbrs%20else%20%22%E2%80%94%22%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg%20%3D%20f%22%7B_avg_nbr%5B_i%5D%3A.2f%7D%22%20if%20_nbrs%20else%20%22%E2%80%94%22%0A%20%20%20%20%20%20%20%20%20%20%20%20_winner%20%3D%20%22%20**%3C**%22%20if%20_nbrs%20and%20_avg_nbr%5B_i%5D%20%3E%20_deg%5B_i%5D%20else%20%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20_rows.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7C%20%7B_names%5B_i%5D%7D%20%7C%20%7Bint(_deg%5B_i%5D)%7D%7B_winner%7D%20%7C%20%7B_flist%7D%20%7C%20%7B_avg%7D%20%7C%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_body%20%3D%20mo.hstack(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B_figG%2C%20mo.md(%22%5Cn%22.join(_rows))%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20widths%3D%5B1.0%2C%201.4%5D%2C%20gap%3D1.0%2C%20align%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%23%20Bigger%20networks%3A%20the%20two%20distributions%20next%20to%20the%20graph.%0A%20%20%20%20%20%20%20%20_kmax%20%3D%20int(max(_deg.max()%2C%20np.nanmax(_avg_nbr)))%0A%20%20%20%20%20%20%20%20_bins%20%3D%20np.arange(0%2C%20_kmax%20%2B%202)%20-%200.5%0A%20%20%20%20%20%20%20%20_figH%2C%20(_ax1%2C%20_ax2)%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3D(7.5%2C%203.6))%0A%20%20%20%20%20%20%20%20_ax1.hist(_deg%2C%20bins%3D_bins%2C%20color%3D%22%23888888%22%2C%20edgecolor%3D%22white%22)%0A%20%20%20%20%20%20%20%20_ax1.axvline(_mean_self%2C%20color%3D%22%23c0223b%22%2C%20linestyle%3D%22--%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidth%3D1.2%2C%20label%3Df%22mean%20%3D%20%7B_mean_self%3A.2f%7D%22)%0A%20%20%20%20%20%20%20%20_ax1.set_title(%22Your%20degree%20%20k%22)%0A%20%20%20%20%20%20%20%20_ax1.set_xlabel(%22k%22)%0A%20%20%20%20%20%20%20%20_ax1.legend(frameon%3DFalse%2C%20fontsize%3D9)%0A%20%20%20%20%20%20%20%20_ax2.hist(_avg_nbr%5B_valid%5D%2C%20bins%3D_bins%2C%20color%3DACCENT%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22white%22)%0A%20%20%20%20%20%20%20%20_ax2.axvline(_mean_nbr%2C%20color%3D%22%23c0223b%22%2C%20linestyle%3D%22--%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidth%3D1.2%2C%20label%3Df%22mean%20%3D%20%7B_mean_nbr%3A.2f%7D%22)%0A%20%20%20%20%20%20%20%20_ax2.set_title(%22Friends'%20average%20degree%22)%0A%20%20%20%20%20%20%20%20_ax2.set_xlabel(%22avg.%20neighbour%20degree%22)%0A%20%20%20%20%20%20%20%20_ax2.legend(frameon%3DFalse%2C%20fontsize%3D9)%0A%20%20%20%20%20%20%20%20for%20_ax%20in%20(_ax1%2C%20_ax2)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.spines%5B%22top%22%5D.set_visible(False)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.spines%5B%22right%22%5D.set_visible(False)%0A%20%20%20%20%20%20%20%20plt.tight_layout()%0A%20%20%20%20%20%20%20%20_body%20%3D%20mo.hstack(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B_figG%2C%20_figH%5D%2C%20widths%3D%5B0.9%2C%201.4%5D%2C%20gap%3D1.0%2C%20align%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20_diff%20%3D%20_mean_nbr%20-%20_mean_self%0A%20%20%20%20if%20_diff%20%3E%201e-9%3A%0A%20%20%20%20%20%20%20%20_verdict%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22your%20friends%20have%20more%20friends%20than%20you%20%E2%80%94%20the%20paradox%20holds%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20elif%20_diff%20%3C%20-1e-9%3A%0A%20%20%20%20%20%20%20%20_verdict%20%3D%20%22friends%20average%20fewer%20%E2%80%94%20unusual%2C%20degree-equal%20networks%20can%20do%20this%22%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_verdict%20%3D%20%22exactly%20equal%20%E2%80%94%20every%20node%20has%20the%20same%20degree%22%0A%20%20%20%20_msg%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20f%22Mean%20degree%20%3D%20**%7B_mean_self%3A.2f%7D**%3B%20mean%20of%20friends'%20averages%20%3D%20%22%0A%20%20%20%20%20%20%20%20f%22**%7B_mean_nbr%3A.2f%7D**%20%E2%80%94%20%7B_verdict%7D.%20No%20psychology%20involved%3A%20it%20is%20%22%0A%20%20%20%20%20%20%20%20%22pure%20structure%2C%20and%20it%20fell%20out%20of%20one%20multiplication%20and%20one%20%22%0A%20%20%20%20%20%20%20%20%22division.%22%0A%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_body%2C%20_msg%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20section4_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%204.%20%60A%20%40%20A%60%20%E2%80%94%20a%20row%20times%20a%20column%0A%0A%20%20%20%20What%20happens%20when%20the%20thing%20you%20multiply%20%24A%24%20by%20is%20%24A%24%20itself%3F%20Cell%0A%20%20%20%20%24(i%2C%20j)%24%20of%20%60A%20%40%20A%60%20is%20**row%20%24i%24%20of%20the%20first%20matrix%20times%20column%0A%20%20%20%20%24j%24%20of%20the%20second**%3A%20pair%20up%20the%20entries%2C%20multiply%20each%20pair%2C%20add%0A%20%20%20%20everything%20up.%0A%0A%20%20%20%20Each%20pair%20asks%3A%20*does%20%24i%24%20know%20%24m%24*%20(row)%2C%20*and%20does%20%24m%24%20know%20%24j%24*%0A%20%20%20%20(column)%3F%20Only%20when%20both%20are%201%20does%20the%20pair%20contribute%20%E2%80%94%20and%20that%0A%20%20%20%20pair%20**is**%20a%20stepping%20stone%3A%20a%20walk%20%24i%20%5Cto%20m%20%5Cto%20j%24%20of%20length%202.%0A%20%20%20%20Cell%20%24(i%2C%20j)%24%20of%20%60A%20%40%20A%60%20therefore%20counts%20the%20walks%20of%20length%202%20%E2%80%94%0A%20%20%20%20the%20friends%20that%20%24i%24%20and%20%24j%24%20have%20in%20common.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s4_widgets(g%2C%20mo)%3A%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20aa_i%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3D_names%2C%20value%3D_names%5B0%5D%2C%20label%3D%22Row%20i%20(first%20matrix)%22%2C%0A%20%20%20%20)%0A%20%20%20%20aa_j%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3D_names%2C%20value%3D_names%5Bmin(2%2C%20len(_names)%20-%201)%5D%2C%0A%20%20%20%20%20%20%20%20label%3D%22Column%20j%20(second%20matrix)%22%2C%0A%20%20%20%20)%0A%20%20%20%20mo.hstack(%5Baa_i%2C%20aa_j%5D%2C%20gap%3D1.0%2C%20widths%3D%22equal%22)%0A%20%20%20%20return%20aa_i%2C%20aa_j%0A%0A%0A%40app.cell%0Adef%20s4_plot(%0A%20%20%20%20A%2C%0A%20%20%20%20NUMBER_THRESHOLD%2C%0A%20%20%20%20aa_i%2C%0A%20%20%20%20aa_j%2C%0A%20%20%20%20clean_axis%2C%0A%20%20%20%20draw_block%2C%0A%20%20%20%20g%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20plt%2C%0A)%3A%0A%20%20%20%20_n%20%3D%20g.vcount()%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20_i%20%3D%20_names.index(aa_i.value)%0A%20%20%20%20_j%20%3D%20_names.index(aa_j.value)%0A%20%20%20%20_A2%20%3D%20A%20%40%20A%0A%20%20%20%20_val%20%3D%20_A2%5B_i%2C%20_j%5D%0A%0A%20%20%20%20if%20_n%20%3C%3D%20NUMBER_THRESHOLD%3A%0A%20%20%20%20%20%20%20%20_fs%20%3D%2011%20if%20_n%20%3C%3D%206%20else%20(9%20if%20_n%20%3C%3D%2010%20else%206.5)%0A%20%20%20%20%20%20%20%20_maxlen%20%3D%20max(len(_nm)%20for%20_nm%20in%20_names)%0A%20%20%20%20%20%20%20%20_left_margin%20%3D%200.35%20%2B%200.21%20*%20_maxlen%20*%20_fs%20%2F%209.0%0A%20%20%20%20%20%20%20%20_top_margin%20%3D%200.6%20%2B%200.21%20*%20_maxlen%20*%20_fs%20%2F%209.0%0A%20%20%20%20%20%20%20%20_gap%20%3D%201.7%0A%0A%20%20%20%20%20%20%20%20_figW%20%3D%2012.0%0A%20%20%20%20%20%20%20%20_x_total%20%3D%20_left_margin%20%2B%203%20*%20_n%20%2B%202%20*%20_gap%20%2B%200.8%0A%20%20%20%20%20%20%20%20_y_total%20%3D%20_n%20%2B%202.6%20%2B%20_top_margin%0A%20%20%20%20%20%20%20%20_figH%20%3D%20min(9.5%2C%20max(3.2%2C%20_figW%20*%20_y_total%20%2F%20_x_total))%0A%20%20%20%20%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(_figW%2C%20_figH))%0A%20%20%20%20%20%20%20%20clean_axis(_ax)%0A%20%20%20%20%20%20%20%20_ax.set_aspect(%22equal%22)%0A%0A%20%20%20%20%20%20%20%20_xe%20%3D%20draw_block(_ax%2C%20A%2C%200%2C%20_names%2C%20_fs%2C%20row_names%3DTrue%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20col_names%3DTrue%2C%20hl_row%3D_i)%0A%20%20%20%20%20%20%20%20_ax.text(_xe%20%2B%20_gap%20%2F%202%2C%20_n%20%2F%202%2C%20%22%40%22%2C%20fontsize%3D15%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20color%3D%22%23333333%22)%0A%20%20%20%20%20%20%20%20_x2%20%3D%20_xe%20%2B%20_gap%0A%20%20%20%20%20%20%20%20_xe2%20%3D%20draw_block(_ax%2C%20A%2C%20_x2%2C%20_names%2C%20_fs%2C%20col_names%3DTrue%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20hl_col%3D_j)%0A%20%20%20%20%20%20%20%20_ax.text(_xe2%20%2B%20_gap%20%2F%202%2C%20_n%20%2F%202%2C%20%22%3D%22%2C%20fontsize%3D15%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20color%3D%22%23333333%22)%0A%20%20%20%20%20%20%20%20_x3%20%3D%20_xe2%20%2B%20_gap%0A%20%20%20%20%20%20%20%20draw_block(_ax%2C%20_A2%2C%20_x3%2C%20_names%2C%20_fs%2C%20col_names%3DTrue%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20hl_cell%3D(_i%2C%20_j))%0A%0A%20%20%20%20%20%20%20%20%23%20The%20products%2C%20under%20the%20columns%20of%20the%20FIRST%20matrix%3A%20entry%20m%0A%20%20%20%20%20%20%20%20%23%20of%20the%20red%20row%20times%20entry%20m%20of%20the%20blue%20column.%0A%20%20%20%20%20%20%20%20for%20_m%20in%20range(_n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_prod%20%3D%20A%5B_i%2C%20_m%5D%20*%20A%5B_m%2C%20_j%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.text(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_m%20%2B%200.5%2C%20_n%20%2B%200.85%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7BA%5B_i%2C%20_m%5D%3Ag%7D*%7BA%5B_m%2C%20_j%5D%3Ag%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20fontsize%3D_fs%20*%200.92%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23222222%22%20if%20_prod%20%3E%200%20else%20%22%23bbbbbb%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_m%20%3C%20_n%20-%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.text(_m%20%2B%201.0%2C%20_n%20%2B%200.85%2C%20%22%2B%22%2C%20ha%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22center%22%2C%20fontsize%3D_fs%20*%200.92%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23bbbbbb%22)%0A%20%20%20%20%20%20%20%20_ax.text(_xe%20%2B%200.6%2C%20_n%20%2B%200.85%2C%20f%22%3D%20%7B_val%3Ag%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22left%22%2C%20va%3D%22center%22%2C%20fontsize%3D_fs%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontweight%3D%22bold%22%2C%20color%3D%22%230e8c6d%22)%0A%20%20%20%20%20%20%20%20_ax.text(%0A%20%20%20%20%20%20%20%20%20%20%20%200%2C%20_n%20%2B%201.9%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22(A%20%40%20A)(%7Baa_i.value%7D%2C%20%7Baa_j.value%7D)%20%20%3D%20%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22red%20row%20times%20blue%20column%20%20%3D%20%20%7B_val%3Ag%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22left%22%2C%20va%3D%22center%22%2C%20fontsize%3D_fs%2C%20color%3D%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_ax.set_xlim(-_left_margin%2C%20_x3%20%2B%20_n%20%2B%200.8)%0A%20%20%20%20%20%20%20%20_ax.set_ylim(_n%20%2B%202.6%2C%20-_top_margin)%0A%20%20%20%20%20%20%20%20_body%20%3D%20_fig%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_body%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22(A%20%40%20A)(%7Baa_i.value%7D%2C%20%7Baa_j.value%7D)%20%3D%20**%7B_val%3Ag%7D**.%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22_Switch%20to%20a%20network%20with%20at%20most%20%7BNUMBER_THRESHOLD%7D%20nodes%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22to%20see%20the%20two%20matrices%20spelled%20out._%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20_common%20%3D%20%5B%0A%20%20%20%20%20%20%20%20_names%5B_m%5D%20for%20_m%20in%20range(_n)%20if%20A%5B_i%2C%20_m%5D%20*%20A%5B_m%2C%20_j%5D%20%3E%200%0A%20%20%20%20%5D%0A%20%20%20%20if%20_i%20%3D%3D%20_j%3A%0A%20%20%20%20%20%20%20%20_interp%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22You%20picked%20the%20diagonal%3A%20every%20neighbour%20of%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Baa_i.value%7D%20is%20a%20walk%20out%20and%20straight%20back%2C%20so%20the%20cell%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22equals%20the%20**degree**%20(%7B_val%3Ag%7D).%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20elif%20_common%3A%0A%20%20%20%20%20%20%20%20_interp%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22The%20nonzero%20pairs%20are%20the%20stepping%20stones%3A%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7B'%2C%20'.join('**'%20%2B%20_c%20%2B%20'**'%20for%20_c%20in%20_common)%7D.%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Baa_i.value%7D%20and%20%7Baa_j.value%7D%20share%20%7B_val%3Ag%7D%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22common%20neighbour%7B's'%20if%20_val%20!%3D%201%20else%20''%7D.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_interp%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22No%20pair%20is%201%20*%201%2C%20so%20%7Baa_i.value%7D%20and%20%7Baa_j.value%7D%20share%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22no%20neighbours%3A%20no%20walk%20of%20length%202%20connects%20them.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_body%2C%20mo.md(_interp)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20section5_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%205.%20Keep%20multiplying%3A%20%60A%20%40%20A%20%40%20A%60%20and%20beyond%0A%0A%20%20%20%20Multiplying%20once%20more%20repeats%20the%20trick%3A%20cell%20%24(i%2C%20j)%24%20of%20%24A%5Ek%24%0A%20%20%20%20(that%20is%2C%20%60A%20%40%20A%20%40%20...%20%40%20A%60%2C%20%24k%24%20times)%20counts%20the%20**walks%20of%0A%20%20%20%20length%20%24k%24**%20from%20%24i%24%20to%20%24j%24%20%E2%80%94%20walks%20may%20revisit%20nodes.%20One%20number%0A%20%20%20%20in%20a%20matrix%2C%20and%20you%20can%20draw%20every%20walk%20it%20counts%20on%20the%20network.%0A%0A%20%20%20%20Three%20things%20fall%20out%20of%20this%20for%20free%3A%20the%20walks%20themselves%2C%20the%0A%20%20%20%20set%20of%20nodes%20you%20can%20reach%20in%20at%20most%20%24k%24%20steps%2C%20and%20%E2%80%94%20on%20the%0A%20%20%20%20diagonal%20of%20%24A%5E3%24%20%E2%80%94%20the%20triangles.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s5_widgets(g%2C%20mo)%3A%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20walk_i%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3D_names%2C%20value%3D_names%5B0%5D%2C%20label%3D%22From%20i%22%2C%0A%20%20%20%20)%0A%20%20%20%20walk_j%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3D_names%2C%20value%3D_names%5Bmin(2%2C%20len(_names)%20-%201)%5D%2C%20label%3D%22To%20j%22%2C%0A%20%20%20%20)%0A%20%20%20%20power_k%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D1%2C%20stop%3D5%2C%20step%3D1%2C%20value%3D2%2C%0A%20%20%20%20%20%20%20%20label%3D%22Walk%20length%20k%22%2C%20show_value%3DTrue%2C%20full_width%3DTrue%2C%0A%20%20%20%20)%0A%20%20%20%20mo.hstack(%5Bwalk_i%2C%20walk_j%2C%20power_k%5D%2C%20gap%3D1.0%2C%20widths%3D%22equal%22)%0A%20%20%20%20return%20power_k%2C%20walk_i%2C%20walk_j%0A%0A%0A%40app.cell%0Adef%20s5_compute(A%2C%20np%2C%20power_k)%3A%0A%20%20%20%20_k%20%3D%20int(power_k.value)%0A%20%20%20%20_M%20%3D%20np.eye(A.shape%5B0%5D)%0A%20%20%20%20for%20_%20in%20range(_k%20-%201)%3A%0A%20%20%20%20%20%20%20%20_M%20%3D%20_M%20%40%20A%0A%20%20%20%20Akm1%20%3D%20_M%20%20%20%20%20%20%20%20%20%20%23%20A%5E(k-1)%2C%20used%20to%20spell%20out%20the%20multiplication%0A%20%20%20%20Ak%20%3D%20_M%20%40%20A%20%20%20%20%20%20%20%20%23%20A%5Ek%0A%20%20%20%20return%20Ak%2C%20Akm1%0A%0A%0A%40app.cell%0Adef%20s5_walks_plot(%0A%20%20%20%20A%2C%0A%20%20%20%20ACCENT%2C%0A%20%20%20%20Ak%2C%0A%20%20%20%20Akm1%2C%0A%20%20%20%20NUMBER_THRESHOLD%2C%0A%20%20%20%20PALETTE%2C%0A%20%20%20%20clean_axis%2C%0A%20%20%20%20draw_graph%2C%0A%20%20%20%20enumerate_walks%2C%0A%20%20%20%20g%2C%0A%20%20%20%20layout_coords%2C%0A%20%20%20%20matrix_with_numbers%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20power_k%2C%0A%20%20%20%20walk_i%2C%0A%20%20%20%20walk_j%2C%0A)%3A%0A%20%20%20%20import%20matplotlib.patches%20as%20_mpatches%0A%20%20%20%20from%20matplotlib.path%20import%20Path%20as%20_MplPath%0A%0A%20%20%20%20_n%20%3D%20g.vcount()%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20_i%20%3D%20_names.index(walk_i.value)%0A%20%20%20%20_j%20%3D%20_names.index(walk_j.value)%0A%20%20%20%20_k%20%3D%20int(power_k.value)%0A%20%20%20%20_count%20%3D%20int(round(Ak%5B_i%2C%20_j%5D))%0A%0A%20%20%20%20%23%20The%20matrix%20already%20knows%20the%20count%3B%20only%20enumerate%20when%20nonzero.%0A%20%20%20%20_walks%20%3D%20enumerate_walks(A%2C%20_i%2C%20_j%2C%20_k%2C%20cap%3D200)%20if%20_count%20%3E%200%20else%20%5B%5D%0A%20%20%20%20_MAX_DRAWN%20%3D%2020%0A%20%20%20%20_drawn%20%3D%20_walks%5B%3A_MAX_DRAWN%5D%0A%0A%20%20%20%20%23%20Walk%20colour%20%3D%20colour%20of%20its%20last%20intermediate%20node%20(the%20m%20in%20the%0A%20%20%20%20%23%20multiplication)%2C%20so%20drawn%20walks%20and%20terms%20match%20by%20colour.%0A%20%20%20%20def%20_walk_color(w)%3A%0A%20%20%20%20%20%20%20%20if%20len(w)%20%3C%203%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20ACCENT%0A%20%20%20%20%20%20%20%20return%20PALETTE%5Bw%5B-2%5D%20%25%20len(PALETTE)%5D%0A%0A%20%20%20%20_fig%2C%20(_axG%2C%20_axE)%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3D(12%2C%205.6))%0A%0A%20%20%20%20%23%20Left%3A%20the%20graph%20with%20walks%20drawn%20as%20bowed%20coloured%20curves.%0A%20%20%20%20draw_graph(_axG%2C%20g%2C%20layout_coords%2C%20vertex_color%3D%22%23c8dde6%22)%0A%20%20%20%20_xs%20%3D%20%5Bc%5B0%5D%20for%20c%20in%20layout_coords%5D%0A%20%20%20%20_ys%20%3D%20%5Bc%5B1%5D%20for%20c%20in%20layout_coords%5D%0A%20%20%20%20_span%20%3D%20max(max(_xs)%20-%20min(_xs)%2C%20max(_ys)%20-%20min(_ys)%2C%201e-9)%0A%20%20%20%20for%20_t%2C%20_w%20in%20enumerate(_drawn)%3A%0A%20%20%20%20%20%20%20%20_col%20%3D%20_walk_color(_w)%0A%20%20%20%20%20%20%20%20_bow%20%3D%20((_t%20%25%205)%20-%202)%20*%200.055%20*%20_span%0A%20%20%20%20%20%20%20%20for%20_a%2C%20_b%20in%20zip(_w%5B%3A-1%5D%2C%20_w%5B1%3A%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_p%20%3D%20np.array(layout_coords%5B_a%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20_q%20%3D%20np.array(layout_coords%5B_b%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20_mid%20%3D%20(_p%20%2B%20_q)%20%2F%202%0A%20%20%20%20%20%20%20%20%20%20%20%20_d%20%3D%20_q%20-%20_p%0A%20%20%20%20%20%20%20%20%20%20%20%20_nrm%20%3D%20float(np.hypot(*_d))%20or%201.0%0A%20%20%20%20%20%20%20%20%20%20%20%20_perp%20%3D%20np.array(%5B-_d%5B1%5D%2C%20_d%5B0%5D%5D)%20%2F%20_nrm%0A%20%20%20%20%20%20%20%20%20%20%20%20_ctrl%20%3D%20_mid%20%2B%20_perp%20*%20_bow%0A%20%20%20%20%20%20%20%20%20%20%20%20_path%20%3D%20_MplPath(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5Btuple(_p)%2C%20tuple(_ctrl)%2C%20tuple(_q)%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B_MplPath.MOVETO%2C%20_MplPath.CURVE3%2C%20_MplPath.CURVE3%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20_axG.add_patch(_mpatches.PathPatch(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_path%2C%20fill%3DFalse%2C%20edgecolor%3D_col%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidth%3D2.2%2C%20alpha%3D0.85%2C%20zorder%3D4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%20%20%20%20_xi%2C%20_yi%20%3D%20layout_coords%5B_i%5D%0A%20%20%20%20_xj%2C%20_yj%20%3D%20layout_coords%5B_j%5D%0A%20%20%20%20_axG.scatter(%5B_xi%5D%2C%20%5B_yi%5D%2C%20s%3D520%2C%20facecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolors%3DACCENT%2C%20linewidths%3D2.5%2C%20zorder%3D8)%0A%20%20%20%20_axG.scatter(%5B_xj%5D%2C%20%5B_yj%5D%2C%20s%3D380%2C%20facecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolors%3D%22%23c0223b%22%2C%20linewidths%3D2.5%2C%20zorder%3D8)%0A%20%20%20%20_extra%20%3D%20f%22%20%20(drawing%20%7Blen(_drawn)%7D%20of%20%7B_count%7D)%22%20if%20_count%20%3E%20len(_drawn)%20else%20%22%22%0A%20%20%20%20_axG.set_title(%0A%20%20%20%20%20%20%20%20f%22%7B_count%7D%20walk%7B's'%20if%20_count%20!%3D%201%20else%20''%7D%20of%20length%20%7B_k%7D%3A%20%22%0A%20%20%20%20%20%20%20%20f%22%7Bwalk_i.value%7D%20(blue%20ring)%20to%20%7Bwalk_j.value%7D%20(red%20ring)%7B_extra%7D%22%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Right%3A%20the%20multiplication%2C%20one%20line%20per%20stepping%20stone%20m.%0A%20%20%20%20clean_axis(_axE)%0A%20%20%20%20if%20_k%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20_v%20%3D%20int(round(A%5B_i%2C%20_j%5D))%0A%20%20%20%20%20%20%20%20_axE.text(%0A%20%20%20%20%20%20%20%20%20%20%20%200.05%2C%200.6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22A(%7Bwalk_i.value%7D%2C%20%7Bwalk_j.value%7D)%20%3D%20%7B_v%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20family%3D%22monospace%22%2C%20fontsize%3D13%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20transform%3D_axE.transAxes%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_axE.text(%0A%20%20%20%20%20%20%20%20%20%20%20%200.05%2C%200.45%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Length%201%20is%20just%20the%20matrix%20entry%3A%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20(%22there%20IS%20a%20direct%20edge.%22%20if%20_v%20else%20%22no%20direct%20edge.%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D11%2C%20va%3D%22top%22%2C%20transform%3D_axE.transAxes%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20elif%20_n%20%3C%3D%20NUMBER_THRESHOLD%3A%0A%20%20%20%20%20%20%20%20_show_all%20%3D%20_n%20%3C%3D%208%0A%20%20%20%20%20%20%20%20_w%20%3D%20max(len(_nm)%20for%20_nm%20in%20_names)%0A%20%20%20%20%20%20%20%20_lhs%20%3D%20%22A%22%20if%20_k%20%3D%3D%202%20else%20f%22A%5E%7B_k%20-%201%7D%22%0A%20%20%20%20%20%20%20%20_lines%20%3D%20%5B(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22(A%5E%7B_k%7D)(%7Bwalk_i.value%7D%2C%7Bwalk_j.value%7D)%20%3D%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22row%20of%20%7B_lhs%7D%20times%20column%20of%20A%3A%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%23333333%22%2C%20True%2C%0A%20%20%20%20%20%20%20%20)%5D%0A%20%20%20%20%20%20%20%20_skipped%20%3D%200%0A%20%20%20%20%20%20%20%20for%20_m%20in%20range(_n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_a%20%3D%20Akm1%5B_i%2C%20_m%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_b%20%3D%20A%5B_m%2C%20_j%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_prod%20%3D%20_a%20*%20_b%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_prod%20%3D%3D%200%20and%20not%20_show_all%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_skipped%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20_col%20%3D%20PALETTE%5B_m%20%25%20len(PALETTE)%5D%20if%20_prod%20%3E%200%20else%20%22%23bbbbbb%22%0A%20%20%20%20%20%20%20%20%20%20%20%20_lines.append((%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%20%20via%20%7B_names%5B_m%5D%3A%3C%7B_w%7D%7D%20%20%7Bint(_a)%7D%20*%20%7Bint(_b)%7D%20%3D%20%7Bint(_prod)%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_col%2C%20_prod%20%3E%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%20%20%20%20%20%20%20%20if%20_skipped%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_lines.append((f%22%20%20(%2B%20%7B_skipped%7D%20terms%20that%20are%200)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%23bbbbbb%22%2C%20False))%0A%20%20%20%20%20%20%20%20_lines.append((%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%20%20total%20%3D%20%7B_count%7D%20walk%7B's'%20if%20_count%20!%3D%201%20else%20''%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%23c0223b%22%2C%20True%2C%0A%20%20%20%20%20%20%20%20))%0A%20%20%20%20%20%20%20%20_dy%20%3D%201.0%20%2F%20(len(_lines)%20%2B%201)%0A%20%20%20%20%20%20%20%20for%20_t%2C%20(_txt%2C%20_col%2C%20_bold)%20in%20enumerate(_lines)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_axE.text(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%200.02%2C%201.0%20-%20(_t%20%2B%201)%20*%20_dy%2C%20_txt%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20family%3D%22monospace%22%2C%20fontsize%3D10%2C%20color%3D_col%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontweight%3D%22bold%22%20if%20_bold%20else%20%22normal%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20transform%3D_axE.transAxes%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_axE.set_title(%22One%20line%20per%20stepping%20stone%20m%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_axE.text(0.5%2C%200.5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22(A%5E%7B_k%7D)(%7Bwalk_i.value%7D%2C%20%7Bwalk_j.value%7D)%20%3D%20%7B_count%7D%5Cn%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Switch%20to%20a%20network%20with%20at%20most%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7BNUMBER_THRESHOLD%7D%20nodes%20to%20see%20the%20terms.%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20fontsize%3D11)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20%23%20The%20full%20A%5Ek%20matrix%2C%20with%20the%20chosen%20cell%20boxed.%0A%20%20%20%20_figM%2C%20_axM%20%3D%20plt.subplots(figsize%3D(6.8%2C%206.2))%0A%20%20%20%20matrix_with_numbers(%0A%20%20%20%20%20%20%20%20_axM%2C%20Ak%2C%20_names%2C%20highlight_cell%3D(_i%2C%20_j)%2C%20cmap%3D%22magma%22%2C%0A%20%20%20%20%20%20%20%20title%3Df%22A%5E%7B_k%7D%20%E2%80%94%20every%20cell%20counts%20walks%20of%20length%20%7B_k%7D%22%2C%0A%20%20%20%20)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20_walk_texts%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%22%20-%3E%20%22.join(_names%5B_v%5D%20for%20_v%20in%20_w)%20for%20_w%20in%20_drawn%5B%3A8%5D%0A%20%20%20%20%5D%0A%20%20%20%20_list_md%20%3D%20(%0A%20%20%20%20%20%20%20%20(%22Walks%20drawn%3A%20%22%20%2B%20%22%3B%20%20%22.join(_walk_texts)%0A%20%20%20%20%20%20%20%20%20%2B%20(%22%20%3B%20...%22%20if%20_count%20%3E%208%20else%20%22%22)%20%2B%20%22.%22)%0A%20%20%20%20%20%20%20%20if%20_count%20%3E%200%20else%0A%20%20%20%20%20%20%20%20f%22No%20walk%20of%20length%20%7B_k%7D%20connects%20%7Bwalk_i.value%7D%20to%20%7Bwalk_j.value%7D.%22%0A%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_fig%2C%20_figM%2C%20mo.md(_list_md)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s5_reach_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Reachable%20in%20at%20most%20%24k%24%20steps%0A%0A%20%20%20%20Add%20the%20powers%20up%3A%20a%20cell%20of%20%60A%20%2B%20A%40A%20%2B%20A%40A%40A%20%2B%20...%60%20is%20positive%0A%20%20%20%20exactly%20when%20SOME%20walk%20of%20length%20at%20most%20%24k%24%20connects%20the%20pair.%0A%20%20%20%20The%20node%20and%20the%20walk%20length%20%24k%24%20above%20drive%20this%20picture%20too%20%E2%80%94%0A%20%20%20%20this%20is%20how%20%22six%20degrees%20of%20separation%22%20and%20epidemic%20horizons%20are%0A%20%20%20%20computed.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s5_reach_plot(%0A%20%20%20%20A%2C%0A%20%20%20%20draw_graph%2C%0A%20%20%20%20g%2C%0A%20%20%20%20layout_coords%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20power_k%2C%0A%20%20%20%20walk_i%2C%0A)%3A%0A%20%20%20%20_n%20%3D%20g.vcount()%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20_s%20%3D%20_names.index(walk_i.value)%0A%20%20%20%20_kmax%20%3D%20int(power_k.value)%0A%0A%20%20%20%20%23%20First%20step%20at%20which%20each%20node%20becomes%20reachable%2C%20via%20matrix%0A%20%20%20%20%23%20powers%3A%20(A%5Ek)%5Bs%2C%20v%5D%20%3E%200%20and%20no%20smaller%20power%20reached%20it%20yet.%0A%20%20%20%20_first%20%3D%20np.full(_n%2C%20-1%2C%20dtype%3Dint)%0A%20%20%20%20_first%5B_s%5D%20%3D%200%0A%20%20%20%20_Acur%20%3D%20np.eye(_n)%0A%20%20%20%20for%20_step%20in%20range(1%2C%20_kmax%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20_Acur%20%3D%20_Acur%20%40%20A%0A%20%20%20%20%20%20%20%20_newly%20%3D%20(_Acur%5B_s%5D%20%3E%200)%20%26%20(_first%20%3C%200)%0A%20%20%20%20%20%20%20%20_first%5B_newly%5D%20%3D%20_step%0A%20%20%20%20_reached%20%3D%20_first%20%3E%200%0A%0A%20%20%20%20%23%20Sequential%20colours%3A%20later%20steps%20%3D%20lighter.%0A%20%20%20%20_cmap%20%3D%20plt.get_cmap(%22viridis%22)%0A%20%20%20%20_step_colors%20%3D%20%5B%0A%20%20%20%20%20%20%20%20_cmap(0.15%20%2B%200.7%20*%20(_step%20-%201)%20%2F%20max(1%2C%20_kmax%20-%201))%0A%20%20%20%20%20%20%20%20for%20_step%20in%20range(1%2C%20_kmax%20%2B%201)%0A%20%20%20%20%5D%0A%20%20%20%20_START_COLOR%20%3D%20%22%23c0223b%22%0A%20%20%20%20_UNREACHED%20%3D%20%22%23e0e0e0%22%0A%20%20%20%20_vcols%20%3D%20%5B%5D%0A%20%20%20%20for%20_v%20in%20range(_n)%3A%0A%20%20%20%20%20%20%20%20if%20_v%20%3D%3D%20_s%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_vcols.append(_START_COLOR)%0A%20%20%20%20%20%20%20%20elif%20_first%5B_v%5D%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_vcols.append(_step_colors%5B_first%5B_v%5D%20-%201%5D)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_vcols.append(_UNREACHED)%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(7.5%2C%206.0))%0A%20%20%20%20draw_graph(_ax%2C%20g%2C%20layout_coords%2C%20vertex_color%3D_vcols)%0A%20%20%20%20_handles%20%3D%20%5Bplt.Line2D(%5B0%5D%2C%20%5B0%5D%2C%20marker%3D%22o%22%2C%20color%3D%22w%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20markerfacecolor%3D_START_COLOR%2C%20markersize%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22start%3A%20%7Bwalk_i.value%7D%22)%5D%0A%20%20%20%20for%20_step%20in%20range(1%2C%20_kmax%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20if%20np.any(_first%20%3D%3D%20_step)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_handles.append(plt.Line2D(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B0%5D%2C%20%5B0%5D%2C%20marker%3D%22o%22%2C%20color%3D%22w%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20markerfacecolor%3D_step_colors%5B_step%20-%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20markersize%3D10%2C%20label%3Df%22reached%20at%20step%20%7B_step%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%20%20%20%20if%20np.any(_first%20%3C%200)%3A%0A%20%20%20%20%20%20%20%20_handles.append(plt.Line2D(%5B0%5D%2C%20%5B0%5D%2C%20marker%3D%22o%22%2C%20color%3D%22w%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20markerfacecolor%3D_UNREACHED%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20markersize%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3D%22not%20reachable%22))%0A%20%20%20%20_ax.legend(handles%3D_handles%2C%20loc%3D%22upper%20right%22%2C%20frameon%3DTrue%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D9)%0A%20%20%20%20_ax.set_title(%0A%20%20%20%20%20%20%20%20f%22From%20%7Bwalk_i.value%7D%3A%20%7Bint(_reached.sum())%7D%20of%20%7B_n%20-%201%7D%20%22%0A%20%20%20%20%20%20%20%20f%22other%20nodes%20within%20%7B_kmax%7D%20step%7B's'%20if%20_kmax%20!%3D%201%20else%20''%7D%22%0A%20%20%20%20)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20_per_step%20%3D%20%5Bint((_first%20%3D%3D%20_step).sum())%20for%20_step%20in%20range(1%2C%20_kmax%20%2B%201)%5D%0A%20%20%20%20_msg%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20%22Newly%20reached%20per%20step%3A%20%22%0A%20%20%20%20%20%20%20%20%2B%20%22%2C%20%22.join(f%22step%20%7B_t%20%2B%201%7D%3A%20%7B_c%7D%22%20for%20_t%2C%20_c%20in%20enumerate(_per_step))%0A%20%20%20%20%20%20%20%20%2B%20%22.%20In%20matrix%20terms%3A%20count%20the%20positive%20entries%20in%20row%20%22%0A%20%20%20%20%20%20%20%20f%22**%7Bwalk_i.value%7D**%20of%20%60A%20%2B%20A%40A%20%2B%20...%20%60%20up%20to%20%24A%5Ek%24%20%22%0A%20%20%20%20%20%20%20%20%22(diagonal%20ignored).%22%0A%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_fig%2C%20_msg%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s5_tri_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Triangles%3A%20the%20diagonal%20of%20%60A%20%40%20A%20%40%20A%60%0A%0A%20%20%20%20Set%20the%20target%20equal%20to%20the%20start%3A%20cell%20%24(i%2C%20i)%24%20of%20%24A%5E3%24%20counts%0A%20%20%20%20round%20trips%20of%20length%203%20%E2%80%94%20leave%20home%2C%20visit%20two%20friends%2C%20come%20back.%0A%20%20%20%20Each%20such%20trip%20traces%20a%20**triangle**.%20On%20an%20undirected%20network%20every%0A%20%20%20%20triangle%20through%20%24i%24%20is%20walked%20twice%20(clockwise%20and%0A%20%20%20%20counter-clockwise)%2C%20so%20triangles%20through%20%24i%24%20%3D%20%24(A%5E3)_%7Bii%7D%20%2F%202%24%2C%20and%0A%20%20%20%20the%20total%20is%20%24%5Cmathrm%7Btr%7D(A%5E3)%2F6%24%20(each%20triangle%20has%203%20corners).%0A%20%20%20%20Triangles%20are%20the%20atoms%20of%20**clustering**%20%E2%80%94%20%22are%20my%20friends%20friends%0A%20%20%20%20with%20each%20other%3F%22%20%E2%80%94%20one%20of%20the%20most-used%20quantities%20in%20network%0A%20%20%20%20science.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s5_tri_plot(%0A%20%20%20%20A%2C%0A%20%20%20%20ACCENT%2C%0A%20%20%20%20EDGE_COLOR%2C%0A%20%20%20%20NUMBER_THRESHOLD%2C%0A%20%20%20%20draw_graph%2C%0A%20%20%20%20g%2C%0A%20%20%20%20is_directed%2C%0A%20%20%20%20layout_coords%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A)%3A%0A%20%20%20%20_n%20%3D%20g.vcount()%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20_A3%20%3D%20A%20%40%20A%20%40%20A%0A%20%20%20%20_diag%20%3D%20np.diag(_A3)%0A%20%20%20%20if%20is_directed%3A%0A%20%20%20%20%20%20%20%20_tri_node%20%3D%20_diag.astype(float)%0A%20%20%20%20%20%20%20%20_total%20%3D%20float(np.trace(_A3)%20%2F%203.0)%0A%20%20%20%20%20%20%20%20_formula%20%3D%20%22directed%3A%20per%20node%20%24(A%5E3)_%7Bii%7D%24%2C%20total%20%24%5C%5Cmathrm%7Btr%7D(A%5E3)%2F3%24%22%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_tri_node%20%3D%20_diag%20%2F%202.0%0A%20%20%20%20%20%20%20%20_total%20%3D%20float(np.trace(_A3)%20%2F%206.0)%0A%20%20%20%20%20%20%20%20_formula%20%3D%20%22undirected%3A%20per%20node%20%24(A%5E3)_%7Bii%7D%2F2%24%2C%20total%20%24%5C%5Cmathrm%7Btr%7D(A%5E3)%2F6%24%22%0A%0A%20%20%20%20_fig%2C%20(_axL%2C%20_axR)%20%3D%20plt.subplots(%0A%20%20%20%20%20%20%20%201%2C%202%2C%20figsize%3D(12%2C%205.2)%2C%20gridspec_kw%3D%7B%22width_ratios%22%3A%20%5B1.3%2C%201.0%5D%7D%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Left%3A%20graph%3B%20triangle%20edges%20highlighted%2C%20counts%20written%20on%20nodes.%0A%20%20%20%20if%20not%20is_directed%3A%0A%20%20%20%20%20%20%20%20_A2%20%3D%20A%20%40%20A%0A%20%20%20%20%20%20%20%20_ecols%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20_ewids%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_e%20in%20g.es%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_u%2C%20_v%20%3D%20_e.source%2C%20_e.target%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_A2%5B_u%2C%20_v%5D%20%3E%200%3A%20%20%23%20the%20edge%20closes%20at%20least%20one%20triangle%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ecols.append(%22%23e07b00%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ewids.append(3.0)%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ecols.append(EDGE_COLOR)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ewids.append(1.2)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_ecols%20%3D%20None%0A%20%20%20%20%20%20%20%20_ewids%20%3D%201.2%0A%20%20%20%20if%20_tri_node.max()%20%3E%200%3A%0A%20%20%20%20%20%20%20%20_sizes%20%3D%20list(16%20%2B%2026%20*%20(_tri_node%20%2F%20_tri_node.max()))%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_sizes%20%3D%20None%0A%20%20%20%20if%20_n%20%3C%3D%20NUMBER_THRESHOLD%3A%0A%20%20%20%20%20%20%20%20_labels%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7B_names%5B_v%5D%7D%5Cn%7B_tri_node%5B_v%5D%3Ag%7D%22%20for%20_v%20in%20range(_n)%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_labels%20%3D%20%5B%22%22%5D%20*%20_n%0A%20%20%20%20draw_graph(_axL%2C%20g%2C%20layout_coords%2C%20vertex_color%3DACCENT%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20vertex_size%3D_sizes%2C%20labels%3D_labels%2C%20label_size%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edge_color%3D_ecols%2C%20edge_width%3D_ewids)%0A%20%20%20%20_axL.set_title(%0A%20%20%20%20%20%20%20%20%22Triangles%20through%20each%20node%22%0A%20%20%20%20%20%20%20%20%2B%20(%22%20%20(orange%20edge%20%3D%20part%20of%20a%20triangle)%22%20if%20not%20is_directed%20else%20%22%22)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Right%3A%20sorted%20bar%20chart.%0A%20%20%20%20_order%20%3D%20np.argsort(-_tri_node)%0A%20%20%20%20_axR.bar(range(_n)%2C%20%5B_tri_node%5B_o%5D%20for%20_o%20in%20_order%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20color%3DACCENT%2C%20edgecolor%3D%22white%22)%0A%20%20%20%20if%20_n%20%3C%3D%2030%3A%0A%20%20%20%20%20%20%20%20_axR.set_xticks(range(_n))%0A%20%20%20%20%20%20%20%20_axR.set_xticklabels(%5B_names%5B_o%5D%20for%20_o%20in%20_order%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rotation%3D90%2C%20fontsize%3D9)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_axR.set_xticks(%5B%5D)%0A%20%20%20%20_axR.set_title(f%22Triangles%20per%20node%20%20(%7B_formula%7D)%22)%0A%20%20%20%20_axR.spines%5B%22top%22%5D.set_visible(False)%0A%20%20%20%20_axR.spines%5B%22right%22%5D.set_visible(False)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20_top%20%3D%20int(np.argmax(_tri_node))%0A%20%20%20%20_msg%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20f%22**Total%20triangles%3A%20%7B_total%3Ag%7D.**%20Most%20triangular%20node%3A%20%22%0A%20%20%20%20%20%20%20%20f%22**%7B_names%5B_top%5D%7D**%20(%7B_tri_node%5B_top%5D%3Ag%7D).%20Divide%20each%20node's%20%22%0A%20%20%20%20%20%20%20%20%22count%20by%20the%20number%20of%20pairs%20of%20its%20neighbours%20and%20you%20get%20the%20%22%0A%20%20%20%20%20%20%20%20%22**local%20clustering%20coefficient**%20%E2%80%94%20same%20diagonal%2C%20one%20division%20%22%0A%20%20%20%20%20%20%20%20%22away.%22%0A%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_fig%2C%20_msg%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20section6_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%206.%20Multiply%20again%20and%20again%20%E2%80%94%20a%20ranking%20emerges%0A%0A%20%20%20%20One%20multiplication%20asked%20about%20neighbours%3B%20two%20asked%20about%20walks%20of%0A%20%20%20%20length%202.%20What%20if%20you%20never%20stop%3F%20Iterate%20%60x%20%3D%20A%20%40%20x%60%2C%20rescaling%0A%20%20%20%20each%20round%20so%20the%20numbers%20stay%20finite.%20Nodes%20with%20well-connected%0A%20%20%20%20neighbours%20pull%20ahead%20%E2%80%94%20having%20many%20walks%20of%20every%20length%20flowing%0A%20%20%20%20through%20you%20is%20what%20%22being%20important%22%20turns%20out%20to%20mean.%20After%20a%0A%20%20%20%20few%20rounds%20the%20bars%20stop%20moving%3A%20the%20network%20has%20settled%20on%20a%0A%20%20%20%20verdict.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20s6_widgets(mo)%3A%0A%20%20%20%20iter_k%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0%2C%20stop%3D30%2C%20step%3D1%2C%20value%3D1%2C%0A%20%20%20%20%20%20%20%20label%3D%22Iterations%22%2C%20show_value%3DTrue%2C%20full_width%3DTrue%2C%0A%20%20%20%20)%0A%20%20%20%20iter_k%0A%20%20%20%20return%20(iter_k%2C)%0A%0A%0A%40app.cell%0Adef%20s6_plot(A%2C%20ACCENT%2C%20g%2C%20iter_k%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_n%20%3D%20g.vcount()%0A%20%20%20%20_names%20%3D%20list(g.vs%5B%22name%22%5D)%0A%20%20%20%20_k%20%3D%20int(iter_k.value)%0A%0A%20%20%20%20_x%20%3D%20np.ones(_n)%20%2F%20np.sqrt(_n)%0A%20%20%20%20for%20_%20in%20range(_k)%3A%0A%20%20%20%20%20%20%20%20_xn%20%3D%20A%20%40%20_x%0A%20%20%20%20%20%20%20%20_nrm%20%3D%20np.linalg.norm(_xn)%0A%20%20%20%20%20%20%20%20if%20_nrm%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%20%3D%20_xn%20%2F%20_nrm%0A%20%20%20%20_x%20%3D%20np.abs(_x)%0A%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_ref%20%3D%20np.array(g.eigenvector_centrality(directed%3Dg.is_directed()))%0A%20%20%20%20%20%20%20%20_ref%20%3D%20np.abs(_ref)%20%2F%20max(1e-12%2C%20np.linalg.norm(_ref))%0A%20%20%20%20except%20Exception%3A%0A%20%20%20%20%20%20%20%20_ref%20%3D%20np.zeros(_n)%0A%0A%20%20%20%20_order%20%3D%20np.argsort(-_ref)%20if%20_ref.sum()%20%3E%200%20else%20np.argsort(-_x)%0A%20%20%20%20_xs%20%3D%20np.arange(_n)%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(11%2C%203.8))%0A%20%20%20%20_ax.bar(_xs%20-%200.2%2C%20%5B_x%5B_o%5D%20for%20_o%20in%20_order%5D%2C%20width%3D0.4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3DACCENT%2C%20edgecolor%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22x%20after%20%7B_k%7D%20iteration%7B's'%20if%20_k%20!%3D%201%20else%20''%7D%22)%0A%20%20%20%20_ax.bar(_xs%20%2B%200.2%2C%20%5B_ref%5B_o%5D%20for%20_o%20in%20_order%5D%2C%20width%3D0.4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23bbbbbb%22%2C%20edgecolor%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20label%3D%22where%20it%20converges%20(igraph%20eigenvector%20centrality)%22)%0A%20%20%20%20if%20_n%20%3C%3D%2030%3A%0A%20%20%20%20%20%20%20%20_ax.set_xticks(range(_n))%0A%20%20%20%20%20%20%20%20_ax.set_xticklabels(%5B_names%5B_o%5D%20for%20_o%20in%20_order%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rotation%3D90%2C%20fontsize%3D9)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20_ax.legend(frameon%3DFalse%2C%20fontsize%3D9)%0A%20%20%20%20_ax.set_title(%22Repeated%20multiplication%20settles%20on%20a%20ranking%22)%0A%20%20%20%20_ax.spines%5B%22top%22%5D.set_visible(False)%0A%20%20%20%20_ax.spines%5B%22right%22%5D.set_visible(False)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20_gap%20%3D%20float(np.linalg.norm(_x%20-%20_ref))%0A%20%20%20%20_msg%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20f%22Distance%20to%20the%20converged%20ranking%20after%20%7B_k%7D%20%22%0A%20%20%20%20%20%20%20%20f%22iteration%7B's'%20if%20_k%20!%3D%201%20else%20''%7D%3A%20**%7B_gap%3A.4f%7D**%20%E2%80%94%20slide%20right%20%22%0A%20%20%20%20%20%20%20%20%22and%20watch%20it%20go%20to%20zero.%5Cn%5Cn%22%0A%20%20%20%20%20%20%20%20%22This%20limit%20is%20**eigenvector%20centrality**.%20Do%20the%20same%20iteration%20%22%0A%20%20%20%20%20%20%20%20%22on%20a%20row-normalised%20%24A%24%20with%20a%20little%20random%20jumping%20and%20you%20%22%0A%20%20%20%20%20%20%20%20%22get%20**PageRank**%20%E2%80%94%20the%20multiplication%20that%20ranked%20the%20web.%20The%20%22%0A%20%20%20%20%20%20%20%20%22last%20section%20maps%20where%20this%20same%20multiplication%20returns%20during%20%22%0A%20%20%20%20%20%20%20%20%22the%20rest%20of%20the%20week.%22%0A%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_fig%2C%20_msg%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20section7_connections(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%207.%20Where%20you%20will%20meet%20this%20again%0A%0A%20%20%20%20-%20**Day%202%20%E2%80%94%20graph%20models%3A**%20is%20my%20network%20surprising%3F%20Compare%20its%0A%20%20%20%20%20%20walk%20and%20triangle%20counts%20against%20a%20random%20network's.%0A%20%20%20%20-%20**Day%203a%20%E2%80%94%20community%20detection%3A**%20communities%20are%20where%20random%0A%20%20%20%20%20%20walks%20stay%20trapped.%0A%20%20%20%20-%20**Day%203b%20%E2%80%94%20link%20prediction%3A**%20the%20simplest%20score%20for%20a%20missing%0A%20%20%20%20%20%20edge%20%24(i%2C%20j)%24%20is%20cell%20%24(i%2C%20j)%24%20of%20%60A%20%40%20A%60%20%E2%80%94%20shared%20friends.%0A%20%20%20%20-%20**Day%203b%20%E2%80%94%20node%20embeddings%3A**%20nodes%20that%20share%20many%20walks%20end%20up%0A%20%20%20%20%20%20with%20similar%20vectors.%0A%20%20%20%20-%20**Day%204%20%E2%80%94%20graphical%20models%3A**%20message%20passing%20is%20%60A%20%40%20x%60%2C%0A%20%20%20%20%20%20repeated.%0A%20%20%20%20-%20**Day%205%20%E2%80%94%20social%20contagion%3A**%20outbreaks%20spread%20along%20the%0A%20%20%20%20%20%20reachability%20rings%3B%20the%20leading%20eigenvalue%20decides%20whether%20they%0A%20%20%20%20%20%20take%20off.%0A%0A%20%20%20%20One%20question%20unlocks%20all%20of%20it%3A%20*which%20walks%20are%20being%20counted%2C%20and%0A%20%20%20%20how%20much%20does%20each%20one%20weigh%3F*%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20footer(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20Javier%20Garcia-Bernardo%20%E2%80%94%20SoDa%20%26%20Utrecht%20University%20%C2%B7%0A%20%20%20%20Network%20Science%20Summer%20School%202026%20%C2%B7%0A%20%20%20%20standalone%20marimo%20companion%20app%20for%20Day%201b.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A