Advanced Topics in Network Science

Author

Sadamori Kojaku

Published

July 27, 2025

1 Graph cut

Another approach from computer science is to treat a community detection problem as an optimization problem. An early example is the graph cut problem, which asks to find the minimum number of edges to cut the graph into two disconnected components.

Specifically, let us consider cutting the network into two communities. Let V_1 and V_2 be the set of nodes in the two communities. Then, the cut is the number of edges between the two communities, which is given by

\begin{align} \text{Cut}(V_1, V_2) = \sum_{i \in V_1} \sum_{j \in V_2} A_{ij} \end{align}

Now, the community detection problem is translated into an optimization problem, with the goal of finding a cut V_1, V_2 that minimizes \text{Cut}(V_1, V_2).

The description of this problem is not complete 😈. Let’s find out what is missing by playing with the optimization problem.

Exercise

:class: tip

Can you identify what is missing in the description of the graph cut problem? Without this, the best cut is trivial. {{ “Graph Cut Problem 🎮”.replace(‘BASE_URL’, base_url) }}

The missing element is a constraint: each community must contain at least one node. Without this, the trivial solution of placing all nodes in a single community would always yield a cut of zero.




:::{#quarto-navigation-envelope .hidden}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyLXRpdGxl"}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXItdGl0bGU="}
[Course Information]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tMQ=="}
[Welcome]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9jb3Vyc2Uvd2VsY29tZS5odG1sV2VsY29tZQ=="}
[About us]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9jb3Vyc2UvYWJvdXQuaHRtbEFib3V0LXVz"}
[Discord]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9jb3Vyc2UvZGlzY29yZC5odG1sRGlzY29yZA=="}
[Using Minidora]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9jb3Vyc2UvbWluaWRvcmEtdXNhZ2UuaHRtbFVzaW5nLU1pbmlkb3Jh"}
[Setup]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9jb3Vyc2Uvc2V0dXAuaHRtbFNldHVw"}
[Introduction]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tMg=="}
[Networks]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9pbnRyby93aHktbmV0d29ya3MuaHRtbE5ldHdvcmtz"}
[M01: Euler Path]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tMw=="}
[A Stroll, Seven Bridges, and a Mathematical Revolution]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDEtZXVsZXJfdG91ci8wMS1jb25jZXB0cy5odG1sQS1TdHJvbGwsLVNldmVuLUJyaWRnZXMsLWFuZC1hLU1hdGhlbWF0aWNhbC1SZXZvbHV0aW9u"}
[Coding Networks in Python]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDEtZXVsZXJfdG91ci8wMi1jb2RpbmcuaHRtbENvZGluZy1OZXR3b3Jrcy1pbi1QeXRob24="}
[Exercises]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDEtZXVsZXJfdG91ci8wMy1leGVyY2lzZXMuaHRtbEV4ZXJjaXNlcw=="}
[Advanced: Sparse Matrices for Large-Scale Networks]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDEtZXVsZXJfdG91ci8wNC1hZHZhbmNlZC5odG1sQWR2YW5jZWQ6LVNwYXJzZS1NYXRyaWNlcy1mb3ItTGFyZ2UtU2NhbGUtTmV0d29ya3M="}
[M02: Small World]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tNA=="}
[Core Concepts]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDItc21hbGwtd29ybGQvMDEtY29uY2VwdHMuaHRtbENvcmUtQ29uY2VwdHM="}
[Efficient Network Representation and Computing Paths]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDItc21hbGwtd29ybGQvMDItY29kaW5nLmh0bWxFZmZpY2llbnQtTmV0d29yay1SZXByZXNlbnRhdGlvbi1hbmQtQ29tcHV0aW5nLVBhdGhz"}
[Exercises and Assignments]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDItc21hbGwtd29ybGQvMDMtZXhlcmNpc2VzLmh0bWxFeGVyY2lzZXMtYW5kLUFzc2lnbm1lbnRz"}
[Appendix - Brief Introduction to igraph]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDItc21hbGwtd29ybGQvMDQtYXBwZW5kaXguaHRtbEFwcGVuZGl4LS0tQnJpZWYtSW50cm9kdWN0aW9uLXRvLWlncmFwaA=="}
[M03: Robustness]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tNQ=="}
[Core Concepts]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDMtcm9idXN0bmVzcy8wMS1jb25jZXB0cy5odG1sQ29yZS1Db25jZXB0cw=="}
[Coding - Network Robustness Analysis]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDMtcm9idXN0bmVzcy8wMi1jb2RpbmcuaHRtbENvZGluZy0tLU5ldHdvcmstUm9idXN0bmVzcy1BbmFseXNpcw=="}
[Exercises and Assignments]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDMtcm9idXN0bmVzcy8wMy1leGVyY2lzZXMuaHRtbEV4ZXJjaXNlcy1hbmQtQXNzaWdubWVudHM="}
[Exercises and Assignments]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDMtcm9idXN0bmVzcy8wNC1hcHBlbmRpeC5odG1sRXhlcmNpc2VzLWFuZC1Bc3NpZ25tZW50cw=="}
[M04: Friendship Paradox]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tNg=="}
[Core Concepts]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDQtbm9kZS1kZWdyZWUvMDEtY29uY2VwdHMuaHRtbENvcmUtQ29uY2VwdHM="}
[Visualizing Degree Distributions in Python]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDQtbm9kZS1kZWdyZWUvMDItY29kaW5nLmh0bWxWaXN1YWxpemluZy1EZWdyZWUtRGlzdHJpYnV0aW9ucy1pbi1QeXRob24="}
[Exercises]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDQtbm9kZS1kZWdyZWUvMDMtZXhlcmNpc2VzLmh0bWxFeGVyY2lzZXM="}
[M05: Clustering]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tNw=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDUtY2x1c3RlcmluZy8wMS1jb25jZXB0cy5odG1sQWR2YW5jZWQtVG9waWNzLWluLU5ldHdvcmstU2NpZW5jZQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDUtY2x1c3RlcmluZy8wMi1jb2RpbmcuaHRtbEFkdmFuY2VkLVRvcGljcy1pbi1OZXR3b3JrLVNjaWVuY2U="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDUtY2x1c3RlcmluZy8wMy1leGVyY2lzZXMuaHRtbEFkdmFuY2VkLVRvcGljcy1pbi1OZXR3b3JrLVNjaWVuY2U="}
[M06: Centrality]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tOA=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDYtY2VudHJhbGl0eS8wMS1jb25jZXB0cy5odG1sQWR2YW5jZWQtVG9waWNzLWluLU5ldHdvcmstU2NpZW5jZQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDYtY2VudHJhbGl0eS8wMi1jb2RpbmcuaHRtbEFkdmFuY2VkLVRvcGljcy1pbi1OZXR3b3JrLVNjaWVuY2U="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDYtY2VudHJhbGl0eS8wMy1leGVyY2lzZXMuaHRtbEFkdmFuY2VkLVRvcGljcy1pbi1OZXR3b3JrLVNjaWVuY2U="}
[M07: Random Walks]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tOQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDctcmFuZG9tLXdhbGtzLzAxLWNvbmNlcHRzLmh0bWxBZHZhbmNlZC1Ub3BpY3MtaW4tTmV0d29yay1TY2llbmNl"}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDctcmFuZG9tLXdhbGtzLzAyLWNvZGluZy5odG1sQWR2YW5jZWQtVG9waWNzLWluLU5ldHdvcmstU2NpZW5jZQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDctcmFuZG9tLXdhbGtzLzAzLWV4ZXJjaXNlcy5odG1sQWR2YW5jZWQtVG9waWNzLWluLU5ldHdvcmstU2NpZW5jZQ=="}
[M08: Embedding]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tMTA="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDgtZW1iZWRkaW5nLzAxLWNvbmNlcHRzLmh0bWxBZHZhbmNlZC1Ub3BpY3MtaW4tTmV0d29yay1TY2llbmNl"}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDgtZW1iZWRkaW5nLzAyLWNvZGluZy5odG1sQWR2YW5jZWQtVG9waWNzLWluLU5ldHdvcmstU2NpZW5jZQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDgtZW1iZWRkaW5nLzAzLWV4ZXJjaXNlcy5odG1sQWR2YW5jZWQtVG9waWNzLWluLU5ldHdvcmstU2NpZW5jZQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDgtZW1iZWRkaW5nLzA0LWFwcGVuZGl4Lmh0bWxBZHZhbmNlZC1Ub3BpY3MtaW4tTmV0d29yay1TY2llbmNl"}
[M09: Graph Neural Networks]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOnF1YXJ0by1zaWRlYmFyLXNlY3Rpb24tMTE="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDktZ3JhcGgtbmV1cmFsLW5ldHdvcmtzLzAxLWNvbmNlcHRzLmh0bWxBZHZhbmNlZC1Ub3BpY3MtaW4tTmV0d29yay1TY2llbmNl"}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDktZ3JhcGgtbmV1cmFsLW5ldHdvcmtzLzAyLWNvZGluZy5odG1sQWR2YW5jZWQtVG9waWNzLWluLU5ldHdvcmstU2NpZW5jZQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDktZ3JhcGgtbmV1cmFsLW5ldHdvcmtzLzAzLWV4ZXJjaXNlcy5odG1sQWR2YW5jZWQtVG9waWNzLWluLU5ldHdvcmstU2NpZW5jZQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1zaWRlYmFyOi9tMDktZ3JhcGgtbmV1cmFsLW5ldHdvcmtzLzA0LWFwcGVuZGl4Lmh0bWxBZHZhbmNlZC1Ub3BpY3MtaW4tTmV0d29yay1TY2llbmNl"}
[Home]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6SG9tZQ=="}
[/index.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L2luZGV4Lmh0bWw="}
[Course]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6Q291cnNl"}
[Welcome]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6V2VsY29tZQ=="}
[/course/welcome.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L2NvdXJzZS93ZWxjb21lLmh0bWw="}
[About]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6QWJvdXQ="}
[/course/about.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L2NvdXJzZS9hYm91dC5odG1s"}
[Discord]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6RGlzY29yZA=="}
[/course/discord.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L2NvdXJzZS9kaXNjb3JkLmh0bWw="}
[Minidora]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6TWluaWRvcmE="}
[/course/minidora-usage.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L2NvdXJzZS9taW5pZG9yYS11c2FnZS5odG1s"}
[Setup]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6U2V0dXA="}
[/course/setup.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L2NvdXJzZS9zZXR1cC5odG1s"}
[Intro]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6SW50cm8="}
[Why Networks?]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6V2h5IE5ldHdvcmtzPw=="}
[/intro/why-networks.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L2ludHJvL3doeS1uZXR3b3Jrcy5odG1s"}
[Foundations]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6Rm91bmRhdGlvbnM="}
[─── M01: Euler Path ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wMTogRXVsZXIgUGF0aCDilIDilIDilIA="}
[Concepts]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6Q29uY2VwdHM="}
[/m01-euler_tour/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMS1ldWxlcl90b3VyLzAxLWNvbmNlcHRzLmh0bWw="}
[Coding]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6Q29kaW5n"}
[/m01-euler_tour/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMS1ldWxlcl90b3VyLzAyLWNvZGluZy5odG1s"}
[Exercises]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6RXhlcmNpc2Vz"}
[/m01-euler_tour/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMS1ldWxlcl90b3VyLzAzLWV4ZXJjaXNlcy5odG1s"}
[Advanced]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6QWR2YW5jZWQ="}
[/m01-euler_tour/04-advanced.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMS1ldWxlcl90b3VyLzA0LWFkdmFuY2VkLmh0bWw="}
[─── M02: Small World ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wMjogU21hbGwgV29ybGQg4pSA4pSA4pSA"}
[/m02-small-world/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMi1zbWFsbC13b3JsZC8wMS1jb25jZXB0cy5odG1s"}
[/m02-small-world/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMi1zbWFsbC13b3JsZC8wMi1jb2RpbmcuaHRtbA=="}
[/m02-small-world/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMi1zbWFsbC13b3JsZC8wMy1leGVyY2lzZXMuaHRtbA=="}
[Appendix]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6QXBwZW5kaXg="}
[/m02-small-world/04-appendix.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMi1zbWFsbC13b3JsZC8wNC1hcHBlbmRpeC5odG1s"}
[─── M03: Robustness ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wMzogUm9idXN0bmVzcyDilIDilIDilIA="}
[/m03-robustness/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMy1yb2J1c3RuZXNzLzAxLWNvbmNlcHRzLmh0bWw="}
[/m03-robustness/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMy1yb2J1c3RuZXNzLzAyLWNvZGluZy5odG1s"}
[/m03-robustness/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMy1yb2J1c3RuZXNzLzAzLWV4ZXJjaXNlcy5odG1s"}
[/m03-robustness/04-appendix.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wMy1yb2J1c3RuZXNzLzA0LWFwcGVuZGl4Lmh0bWw="}
[Core Topics]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6Q29yZSBUb3BpY3M="}
[─── M04: Friendship Paradox ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wNDogRnJpZW5kc2hpcCBQYXJhZG94IOKUgOKUgOKUgA=="}
[/m04-node-degree/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNC1ub2RlLWRlZ3JlZS8wMS1jb25jZXB0cy5odG1s"}
[/m04-node-degree/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNC1ub2RlLWRlZ3JlZS8wMi1jb2RpbmcuaHRtbA=="}
[/m04-node-degree/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNC1ub2RlLWRlZ3JlZS8wMy1leGVyY2lzZXMuaHRtbA=="}
[─── M05: Clustering ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wNTogQ2x1c3RlcmluZyDilIDilIDilIA="}
[/m05-clustering/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNS1jbHVzdGVyaW5nLzAxLWNvbmNlcHRzLmh0bWw="}
[/m05-clustering/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNS1jbHVzdGVyaW5nLzAyLWNvZGluZy5odG1s"}
[/m05-clustering/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNS1jbHVzdGVyaW5nLzAzLWV4ZXJjaXNlcy5odG1s"}
[─── M06: Centrality ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wNjogQ2VudHJhbGl0eSDilIDilIDilIA="}
[/m06-centrality/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNi1jZW50cmFsaXR5LzAxLWNvbmNlcHRzLmh0bWw="}
[/m06-centrality/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNi1jZW50cmFsaXR5LzAyLWNvZGluZy5odG1s"}
[/m06-centrality/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNi1jZW50cmFsaXR5LzAzLWV4ZXJjaXNlcy5odG1s"}
[Advanced Topics]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6QWR2YW5jZWQgVG9waWNz"}
[─── M07: Random Walks ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wNzogUmFuZG9tIFdhbGtzIOKUgOKUgOKUgA=="}
[/m07-random-walks/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNy1yYW5kb20td2Fsa3MvMDEtY29uY2VwdHMuaHRtbA=="}
[/m07-random-walks/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNy1yYW5kb20td2Fsa3MvMDItY29kaW5nLmh0bWw="}
[/m07-random-walks/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wNy1yYW5kb20td2Fsa3MvMDMtZXhlcmNpc2VzLmh0bWw="}
[─── M08: Embedding ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wODogRW1iZWRkaW5nIOKUgOKUgOKUgA=="}
[/m08-embedding/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wOC1lbWJlZGRpbmcvMDEtY29uY2VwdHMuaHRtbA=="}
[/m08-embedding/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wOC1lbWJlZGRpbmcvMDItY29kaW5nLmh0bWw="}
[/m08-embedding/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wOC1lbWJlZGRpbmcvMDMtZXhlcmNpc2VzLmh0bWw="}
[/m08-embedding/04-appendix.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wOC1lbWJlZGRpbmcvMDQtYXBwZW5kaXguaHRtbA=="}
[─── M09: Graph Neural Networks ───]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI64pSA4pSA4pSAIE0wOTogR3JhcGggTmV1cmFsIE5ldHdvcmtzIOKUgOKUgOKUgA=="}
[/m09-graph-neural-networks/01-concepts.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wOS1ncmFwaC1uZXVyYWwtbmV0d29ya3MvMDEtY29uY2VwdHMuaHRtbA=="}
[/m09-graph-neural-networks/02-coding.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wOS1ncmFwaC1uZXVyYWwtbmV0d29ya3MvMDItY29kaW5nLmh0bWw="}
[/m09-graph-neural-networks/03-exercises.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wOS1ncmFwaC1uZXVyYWwtbmV0d29ya3MvMDMtZXhlcmNpc2VzLmh0bWw="}
[/m09-graph-neural-networks/04-appendix.html]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLWludC1uYXZiYXI6L20wOS1ncmFwaC1uZXVyYWwtbmV0d29ya3MvMDQtYXBwZW5kaXguaHRtbA=="}

:::{.hidden .quarto-markdown-envelope-contents render-id="Zm9vdGVyLWxlZnQ="}
Copyright 2024, Sadamori Kojaku
:::

:::



:::{#quarto-meta-markdown .hidden}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLW1ldGF0aXRsZQ=="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLXR3aXR0ZXJjYXJkdGl0bGU="}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLW9nY2FyZHRpdGxl"}
[Advanced Topics in Network Science]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLW1ldGFzaXRlbmFtZQ=="}
[]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLXR3aXR0ZXJjYXJkZGVzYw=="}
[]{.hidden .quarto-markdown-envelope-contents render-id="cXVhcnRvLW9nY2FyZGRkZXNj"}
:::




<!-- -->

::: {.quarto-embedded-source-code}
```````````````````{.markdown shortcodes="false"}
# Graph cut

Another approach from computer science is to treat a community detection problem as an *optimization* problem.
An early example is the **graph cut** problem, which asks to find the minimum number of edges to cut the graph into two disconnected components.

Specifically, let us consider cutting the network into two communities. Let $V_1$ and $V_2$ be the set of nodes in the two communities.
Then, the cut is the number of edges between the two communities, which is given by

$$
\begin{align}
\text{Cut}(V_1, V_2) = \sum_{i \in V_1} \sum_{j \in V_2} A_{ij}
\end{align}
$$

Now, the community detection problem is translated into **an optimization problem**, with the goal of finding a cut $V_1, V_2$ that minimizes $\text{Cut}(V_1, V_2)$.

The description of this problem is not complete 😈. Let's find out what is missing by playing with the optimization problem.

::: {.callout-note title="Exercise"}
:class: tip

Can you identify what is missing in the description of the graph cut problem? Without this, the best cut is trivial. {{ "<a href='BASE_URL/vis/community-detection/index.html?scoreType=graphcut&numCommunities=2&randomness=1&dataFile=two-cliques.json'>Graph Cut Problem 🎮</a>".replace('BASE_URL', base_url) }}

::: {.callout collapse="true"}
## Click to reveal the answer!

The missing element is a constraint: each community must contain at least one node. Without this, the trivial solution of placing all nodes in a single community would always yield a cut of zero.

```````````````````