{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Your feedback\n", "\n", "\n", "**Your feedback is important to me!**\n", "If you haven't yet, **please** (please!!!), fill the [Week 5 - Mid-term Feedback Form](https://learn.inside.dtu.dk/d2l/lms/survey/user/surveys_list.d2l?ou=187754) on DTU Learn. It only takes few minutes. \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Overview\n", "\n", "In this class, we will learn more about networks. You will get an overview of concepts such as Assortativity, Centrality and Communities.\n", "The lecture is structured as follows.\n", "\n", "* __Part 1__: Learn about Centrality and Assortativity through a lecture. Apply the concepts to undertand a bit more about the structure of our network of Computational Social Scientists. \n", "* __Part 2__: Learn about Community Detection with a lecture and an exercise related to the famous [Zachary Karate Club Network](https://en.wikipedia.org/wiki/Zachary%27s_karate_club). Then, apply what you have learned to study the network of Computational Social Scientists.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Part 1: Centrality and Assortativity\n", "\n", "We will start by learning about some advanced concepts in network science: Centrality and Assortativity. Then, we will apply these concepts to learn a bit more about our network of scientsits. \n", "\n", "> **_Video lecture:_** [Network measures.](https://youtu.be/a_J5lV4KT3Q)\n", ">\n", "> **_Reading_**: Learn about assortativity by reading [Chapter 7](http://networksciencebook.com/chapter/7#introduction7). The important parts are in sections [7.2](http://networksciencebook.com/chapter/7#assortativity) and [7.3](http://networksciencebook.com/chapter/7#measuring-degree)." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEAAUDBAgIBgUFBQUGBQYGBwUGBwcHBgUGAgICBgUGBgYFBQUHChALBwgOCQYFDRUYDhERExMTBxcWGBYSGBASExIBBQUFBwYHBQgIBRIIBQgSEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEv/AABEIAWgB4AMBIgACEQEDEQH/xAAcAAEBAQADAQEBAAAAAAAAAAAAAQIDBQYEBwj/xABDEAEAAAMDBQwHBgQHAAAAAAAAAQIRAwQFF1RVktIGFBUxUlOUlaLR09QSExaBkZOhByFBYYLwUXGjsTJCQ2SEsuH/xAAUAQEAAAAAAAAAAAAAAAAAAAAA/8QAFBEBAAAAAAAAAAAAAAAAAAAAAP/aAAwDAQACEQMRAD8A/jIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAfoGRndJoSXrLBPMmRndJoSXrLBPMg/Px76b7HN0cOPBZessF8wzkf3RcXA0vWODeYB4Me9yP7otDS9Y4N5gyP7otDS9Y4N5gHgh73I/ui0NL1jg3mGY/ZBui0NL1jg3mAeEHu8kO6HQ0vWODeYTJHuh0PL1hg/mAeFHuske6HQ8vWGD+YMke6HQ8vWOD+YB4Ue6j9ke6GH3xweXrHB/MM5Jt0GiJesMH8wDw49xknx/REvWGEeYTJPj+iJesMI8wDxA9vknx/REvWGEeYMlGP6Il6wwjzAPED2+SjH9ES9YYR5gyUY/oiXrDCPMA8QPaZLMd0TL0/CfHMlmO6Jl6fhPjg8WPaZLMe0TL0/CfHMlmPaJl6fhPjg8WPaZLMd0TL0/CfHZn+zDHIU9LCpYV/32FRr8LcHjR7DJnjei5enYX47E32b4zD7o4ZL03DPGB5Iesyc4zo2HTcN8ZnJ5jGjYdMw3xgeVHqsnuMaOh0zDfGcc+4PFYf4sPhD/l4f4oPMj0UdxGJ8e8YdKuPip7F4nmMOk3HxQeeHoI7jMS/G5Q6TcfEZjuQxGHHc4dIufiA6Ed3Hcpf4cd0h0i6eInstf8ANIdIuniA6UdxHc1feLesPn3XbT2bvubQ+fddsHUDs+Ab3m8Pm3fbSOBXrN4fNu+2DrR2PAl65iHzbDaSOC3mHHYQ+bYcesDrx9/BF45mHzLHaTgm8czD5ljtA+EfdwTeOZ/qWO0zHDLeH3Rsv6lltA+MfZwbbc127LaODbbmu3ZbQPjH1xw225rt2XFrM7xteb7UneD5h9O8bXm+1J3m8bXm+1J3g+YfTvK15vtSd7MbnacjtSd4OAc29Z+R2pO83rPye1J3g4Rzb1n5Pak7zes/J7UneDvfanEdI2mpYbCR3U4jpG01LDYdOA7f2qxH8cQtPl2GwTbpsQjx3+0j+iw2XUAO19pL/n9pqWOye0l/z+01LHZdV7z3g7X2kv8An9pqWOysN0l/z61+XY7LqfeA7b2kv+fWvy7HZPaS/wCfWmpY7LqapT84g7f2jv8An1pqWOyzHdBfvxv88f02Oy6qn5xWv5QB2XD98z201LKn/U4fvmfT6tjsutr/ACPdAHYwx++Z9Pq2OyvD19z6bVsdl1kf5IDs447fPxvs8f02WynDt8zyfVstl1oDsuHb5nk+rZbJw7fM8n1bLZdaA7Hhy+Z3Pq2WycOXzO59Wy2XXfvjI/v7wdjw7fM8n1bLZOHb5nc+rZbLrf3xn74wdjHHb5nc+rZ7JDHb3+N8nh+my+/suu+KU/mDsJsZvUeO9Tx/TZ9yQxi85zPq2fc+GHv+JH3g+7hi851Pq2fccMXnOJ9WTufBRQfdwxec4n1ZO5x2mJXiPHeJ4/pk7nylQfVDEbfOJ/hJ3HCVvz8/wk7nyKD6eErfn5/hJ3Eb9bR/15/hL3PmhA+PxB9G/bbnp/hL3Mxv1tz0/wAJe5wRj+/yQHPG9WnH62PZr/ZN82nOx7Pc4Yfv+IDn3zac5H6Jvm05z+zhAcsbefnI/RPXz85H6OMgDcbeflx+hC2n5cfowA5PXT8v+yRtZvxnj9GAGvWTcuP0PWTcuP0SpUF9ZNyo/RfTm5TNU94N+nNyj05uU4/eVBv1s0P8yesm5TNKrCAL6c3K/wDWYzfxrEigHpfnHuPS/OIA5wAAAAAAAAAASoKlSqAsUAAFBBKlQKlQAAAAAAAAAAAEhEqCpGKVAAAAAAAAAAAAAAAASoLFlaoCwIxSAAAAADnAAAAAABIgqVQBaoAAAAAEYpUiAAAAAAAAAAAAACIBAAAAAAAAAAAAAAAAAEBWVQASCgQAAAAABzgAAkQVIoAAAAAAVAEqARAAAAAAAAAAAABIgqVQBaoAAAAAAAAAAAAAAJEFGWoAIgAACQUAAAAAAAc1SqAAAAAAFQCqVAWqAAAAAAAAAAAAAAhGKRBakUAAAAAAAAAAAAAAAASILVEWAFAjFAAAAAAAAAAAAAcoAAEQBKgLVAAAAAAAAAAAAAACMWagtSqAAAAAAAAAAAAAAAAAAAJURYAUCMUAiQAAAAAAAAAAAAAHJUqAFSoAAAAAAAAAAAAAAAkYpVYpEAAAAAAAAAAAAAAAAAAEqVEBalUAAAAAAAAAAAAAAAAAAAcgAAAAAAAAAAAAAAkSoEUqAAAAAAAAAAAAAAAAAAAJEqRQGiiAIAAAAAAAAAAAAAAAAAAADkAAAAAAAABkGhkBYoAAAAAAAAAAAAAAAAAAAAAJFFigARQFAAAAAAAAAAAAAAAAAAAAAByAAAgKJUqCiVQGmQAAAAAAAAAAAAAAAAAAABKgolSoKRSqAqAAAAAAAAAAAAAAAAAAAAAAAAADkEqVAqRQAAAAAAAAAAAAAAAAAAAAAAiAJVQEVAQAEgpQAAAAAAAAAAAAAAAAAAAAAAAAAABoAAAAAAAAAAAAAAAAAAAAAASpAFSKpEEWEUAIxAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABoAAAAAAAAAAAAAAAAAAAAAGVQBYxSAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA0AAAAAAAAAAAAAAJFAaEgoAiAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA0AAAAAAABQqIC1KsgKUIFQEWKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA0AABEAilSIFRAFKItQKItUAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABocfpRPSiDdSrFSoNkWKlQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQaGalQQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAH//Z\n", "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import YouTubeVideo\n", "YouTubeVideo(\"a_J5lV4KT3Q\", width=600)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Network Analysis in Computational Social Science\n", "\n", "This week, we'll delve deeper into the network of Computational Social Scientists, focusing on advanced network features. If your network is composed of multiple components, concentrate on the giant connected component (GCC) for the exercises below. Utilize the network constructed in [Week 4](https://github.com/lalessan/comsocsci2024/blob/main/lectures/Week4.ipynb).\n", "\n", "> __Exercise 1: Mixing Patterns and Assortativity__ \n", ">\n", "> __Part 1: Assortativity Coefficient__ \n", "> 1. *Calculate the Assortativity Coefficient* for the network based on the country of each node. Implement the calculation using the formula provided during the lecture, also available in [this paper](https://arxiv.org/pdf/cond-mat/0209450.pdf) (equation 2, here for directed networks). **Do not use the NetworkX implementation.**\n", ">\n", "> __Part 2: Configuration model__\n", "> In the following, we are going to assess the significance of the assortativity by comparing the network's assortativity coefficient against that of random networks generated through the configuration model. \n", ">\n", "> 2. *Implement the configuration model* using the _double edge swap_ algorithm to generate random networks. Ensure each node retains its original degree but with altered connections. Create a function that does that by following these steps:\n", "> - **a.** Create an exact copy of your original network.\n", "> - **b.** Select two edges, $e_{1} = (u,v)$ and $e_{2} = (x,y)$, ensuring *u != y* and *v != x*.\n", "> - **c.** Flip the direction of $e_{1}$ to $e_{1} = (v,u)$ 50% of the time. This ensure that your final results is not biased, in case your edges were sorted (they usually are). \n", "> - **d.** Ensure that new edges $e_{1}' = (e_{1}[0],e_{2}[1])$ and $e_{2}' = (e_{2}[0],e_{1}[1])$ do not already exist in the network.\n", "> - **e.** Remove edges $e_{1}$ and $e_{2}$ and add edges $e_{1}'$ and $e_{2}'$.\n", "> - **f.** Repeat steps **b** to **e** until you have performed _E*10_ swaps, where E is the total number of edges.\n", "> 3. *Double check that your algorithm works well*, by showing that the degree of nodes in the original network and the new 'randomized' version of the network are the same.\n", ">\n", ">\n", "> __Part 3: Analyzing Assortativity in Random Networks__ \n", ">\n", "> 4. *Generate and analyze at least 100 random networks* using the configuration model. For each, calculate the assortativity with respect to the country and plot the distribution of these values. Compare the results with the assortativity of your original network to determine if connections within the same country are significantly higher than chance.\n", ">\n", "> __Part 4: Assortativity by Degree__\n", ">\n", "> 5. *Calculate degree assortativity* for your network using the formula discussed in the lecture.\n", "> 6. *Compare your network's degree assortativity* against that of 100 random networks generated via the configuration model. Analyze whether your network shows a tendency for high-degree scientists to connect with other high-degree scientists and vice versa. \n", ">\n", "> __Part 5: Reflection questions__ \n", "> 7. *Assortativity by degree.* Were the results of the degree assortativity in line with your expectations? Why or why not? \n", "> 8. *Edge flipping.* In the process of implementing the configuration model, you were instructed to flip the edges (e.g., changing *e_1* from (u,v) to (v,u)) 50% of the time. Why do you think this step is included? \n", "> 9. *Distribution of assortativity in random networks.* Describe the distribution of degree assortativity values you observed for the random networks. Was the distribution pattern expected? Discuss how the nature of random network generation (specifically, the configuration model and edge flipping) might influence this distribution and whether it aligns with theoretical expectations. \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "> **Exercise 2: Central nodes.** Remember to write your answers in the notebook. \n", "> * Find the 5 most central scientists according to the closeness centrality. What role do you imagine scientists with high closeness centrality play? \n", "> * Find the 5 most central scientists according to eigenvector centrality. \n", "> * Plot the closeness centrality of nodes vs their degree. Is there a correlation between the two? Did you expect that? Why? \n", "> * Repeat the two points above using eigenvector centrality instead. Do you observe any difference? Why?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Part 2: Community detection." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will continue the analysis of our network of Computational Social Scientists.\n", "We will start by learning about community detection with a lecture from my colleague Sune Lehmann.\n", "\n", "> **_Video Lecture_**: Communities in networks. \n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEABALDA4MChAODQ4SERATGCgaGBYWGDEjJR0oOjM9PDkzODdASFxOQERXRTc4UG1RV19iZ2hnPk1xeXBkeFxlZ2MBERISGBUYLxoaL2NCOEJjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY//AABEIAWgB4AMBIgACEQEDEQH/xAAbAAACAwEBAQAAAAAAAAAAAAAAAgEDBAUGB//EADwQAAIBAwICBQsEAgEDBQAAAAABAgMEESExBRIyQVFTkgYTFiIjM2FxkdHSFBVSgUJDsSQ0oWJygsHh/8QAGAEBAQEBAQAAAAAAAAAAAAAAAAECAwT/xAAeEQEBAQEBAQEAAwEAAAAAAAAAARECMRIhA0FRE//aAAwDAQACEQMRAD8A+fgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAdaXk/dxSbqUdf/U/sL+w3XeUfq/sTYuVywOg+EXCeOel9X9iP2i4/nT+r+w1MYAOh+0XH86X1f2D9nuP50vq/sNMc8Do/s1x/Ol9X9g/Zrn+dL6v7DYuOcB0Hwe4X+VP6v7ELhFd/50vq/sNhjAB0lwS5e1Sj9X9if2O5/nR+r+w2GOYB0/2O5/nR+r+wfsdz/Oj9X9hsMcwDp/sd1/Oj9X9g/Y7nvKP1f2GwxzAOp+w3XeUfq/sT+wXXeUfq/sNhlcoDrej933lHxP7E+jt33lDxP7D6hlcgDsLybvH/ALKHif2J9GrzvaHif2H1D5rjAdn0Zve9t/E/sNDyXvZ7VbfxS+w2GVxAO96JX/e23il9g9E7/vbbxS+w2GVwQO96JX/fW3il9g9Er/vrbxS+w2GVwQO/6I3/AH1t4pfiHojf99beKX4jYZXAA7/ojf8AfW3il+IeiPEO+tvFL8RsMcADvvyR4gv91t4pfiC8kOIP/dbeKX4jYZXAA7/ojf8AfW3il+JPohxDvrbxS/EbDK8+B6D0Q4h31t4pfiR6IcQ7628UvxGwyuAB3/RG/wC+tvFL7EPySv1/ttvFL7DYZXBA73onf97beKX2Ifknfr/bbeKX2GwyuEB3l5J37/223il9iPRS/wC9tvFL7DYZXCA7j8lr5f7bfxS+xHove97b+KX2GwyuIB2vRi97238T+xHo1ed7Q8T+w+oZXGA7fove97b+KX2D0Wvu9t/FL7D6hlcQDueit93tv4pfYPRa+7238UvsPqGVwwOzLyavI71bfxP7AvJq8f8AtoeJ/YbDK4wHY9G7zvKHif2Ffk9dr/ZQ8T+w2GVyQOjLgtzGWHOl9X9hlwO5e1Sj9X9hsMrmAdT9huu8o/V/Yj9iuu8o/V/YfUPmvT1OhEqLavu4lKObbLU6bIJqdNkI0ykkgkgZDCoYKMCygmMSBSuaBbGonuGBXDsAtySUpuJYpJkU6Fe6JQr6QFrJRDJRKsOh0IixEUyHQiHQEllDcrLaG5Roewq3G6imc1B5eyCL+ohNGOpcupnkemOpmenOryvmrJ5010GrjqtrtKKl1CK0nFv5mCU3FYnUj8nIonWhB5jNZfYs5Gny6NDiVKpPkk+SWcYZtTPN1bx49pThL4Nai0+IcrXLUlBdSzlDTHppbBDY4X7xOEllwmuvBttOMWtfEXNU5vqloVMdDrGK1OOd0WBEMgkAIFkMLICERIZCyAIkPcmJD3Cq5biMeW4jMqgR7jiPcCxDoVDxQAJJ9g8hVHrYRTJCl0yp9ZQdRTLcuexRUeoGKv7wtp7FVbposp7EU7IZLICrqvuolJdV91EoNMM9TpsUap02KjSJJIJQQ6JRCJRFBIE4AgCQAjGRXHGxYDIpIya3JTzInCYmGpAaGShVsMiVYdDoRDoKdDoVDIgYsoblZZR01YF1WahBts4ta7lzy5Vzf2Rxe8U5ebhlJbtHIjyuWZOr/WhSNVa7UdccsmUq5dRc0VJ/1lFValGfL7SfLnVzzkZV6FvH2c6zeMes00FWwry2cYrsb1RRc3E4f4p/+1//AEZ61151/wCL+CM8ptPVNfMsia007tTerwx9G20s57ZGHl5vmXU45SjLOE+ouBa1SUZaPT4MaNWdWLahhJZyaqNHLnmOYvRrqQ1ShGFF8meZxXyZNhlJbcSrwWOd9mrPSWfFlU5KSi28dJ7Hl3bOEHJZbWrN9g+Zqrjlz/igY9fGSksolmXh0+enhyybMIMkFkWaCyQCoiRKIkARFe40SHuBVLcRjy3EI0hiPcdlctyC5FsEUxZfTAhoVlkhWsIIpmVPctqMpbKJexlrGrqM1fcDHV6SLKexVV3RbT2CnZBLFCtFb3USg0VvcxM2SsM9Tpsgmp02KaZMShSdQGQ6K0OiKZEkEagSGCMsMsB8BgXLJyRUkLpEohdIIslJR3Gi8ox8QqeagpFlnVVSmnkNRrRYitDxIqxDoRDogk53EbyVPFKk8PGZNGq8q+aoSkt+o81VrSbcm8vtKHr1o41bk/gZJ3zi+XEmvmU1OebzuJyyf+JqSF1plX84nhKS7Huih0ZSeVGMV8xqcJdSfyZspUamPgTcWTWH9O89T+Rqo29ScMNZXYzo21m3hyjlHUt7JYeY4M3pufxuJQ4drtob6fDlplanXjQS2RZ5pLqM66TmOfC0jCLSW4lS0TWEdNwwVyjqTVxx69m8Z301RRQjGhzaYedY7/2dyVNMwX1pmPPHSSLKx1yusbunzc0W12pnag1OKcXlHkKeVLmT+aZ2uG3Elik3o9jccbHWwQ0JmQKUisnSIkStURIAjsK9xo7CvcKqluKNLcUilZVLctZTUeGQWxZopsyQkjTTYFjIexDepDehUUVCpltTdlTAZdEz19Fk0rYqqpNAc2rqyylsFaOGRTCrCGDIA1VvcozGmv7hfMymmVFTpsUap02KGTIkUkoZDIVEoinJIJAgAACQAGQSQukSQukBm4unK2eDDwW4eXCT2OnxDDt5ZPOWlXzd4mtmzU8HsIsdFFCXNTTL4mG1iHRWh0Bj4rUcLZ40T3PNVakOv6Hd49LFGC6snnqNN1rhL+ywa6FDnx6uDZCyTexbQp4N1KK6jna7c8stPh/yZrpWiSw0aYR07C6NPTczreK6VBRNCikiYwUVqyXNbRWQoS7ETgFzPcbAQkkVSWpe4lU4hVOzFnHmTyPJYFA4d5SdKq5QHtK6hUjJr1kaL2OrOc8wn2r4G449R7ClNVacZpbhJHM4Hc88JUW9tUdSRtyoiLMaJEwiI7CvcaOwr3CqpbiDy3EZFQzHeS5Y5NbMPEHimwGs6nOjoQehx+HS0OvB+qREc2Zlj2M6ftDR1AUVCIrI1Qq5miixlMy2OqEqbgYLjpCU9yy56RVDcKsyQSQBrr+4/syGuv7j+zGaZVVOmxSanSZBWUkkEgSiUQiUA6JFQxFAAAEoGCBgHUEekieoiPSAp4nLFszyylifN8cnpuLP/pmeXNcp09bw2pz0I/I3xOJwOrmil2HaiYrcWodFcR4kVyvKBvzUFjTtOZw2n605Y+B1OPZdOlrpnYw2OlN/MXxefW+l8djXSfVFf2ZKS7djVTk30Vp2nKvRGmKk92WrkitZ/wDkogl1stjGKltkjR1OmtN2PGqs6R1BKJK5chDLnfwG5e1kZeNEK4t7tlEtLtFwu0aMIL4/MHhLYCppFUtC5tN6FU92Bgu1nQ51aL5Wde4p80crc5twmjcc+ong9ZUr6HM9HoeomeOh7OpGXYz1sJqpRhNapo241ZEiZMSJhlEdhXuNDYV7hVMtxRpbisilZg4j7pm9nP4j7pgc+0ufN5XxO7Z1PO08nk4dJ/M9Nwx+xRbHOW618iUsk5GZCRG1VQqZbU3EAeC9Urqoup9Erq7gc+53KYbl93uUQ3AsIAArZX/7f+zGa63uP7MeTTKqfSICfSBFZSCAkCSUQSgGW4wi3HIoJIJQEkMkGAdREekHUEekgMfGZYtzzR6Ljb9gedNRmutwOpibj8T0cWeS4ZPkul8T1dJ5gjPTfPi9DoriWIy0wcap81opfxZyrF+q0ehuaSrW8oPrWh5m3bpV3F6POB/Sz116eyNcE8aaIx0n6upfGrFL1noc3olaoxj25L4QS1MMb2hDRyNVG8pT0T3Ji61pJInrxgVS5ojprGSgByil6xluK8qcZcv9HOuqlzXkop4j8CxK6lS7pQ/zRjq3aezMlLh1WcvXk4o3UuHUILDqNv4sJ+sjvJcyxqjRC7UoessmuNpSjF8qiZ6lBLRIGU26OfxCHLiS2ZtpLRrs2Kb+ObaTW61EL45jWzPS2PLHh9Nzlh42OFZxVWrGL1TO5GOIqPUtC2s88S+tMXlZWxE9hafqxSyNPY1Lrl3z80Q2Fe40NhGVhVLpCMaW4rI0VmDiPuWbmYOIe6YHEpQcpPC6z0fDU1SWTk8PpqTZ3KCUYpItZk/tc2PHYrLIdEgpqblZbU3K+oKsp9ESsW0l6olZBHOuzNDc1Xi0MkNwq0AAK11vcf2YjZW9w/mYjTKufSBEVOkCKyYkgkCQQAQMhhBwqSUKSgHFYwr3AgI9IlrQXOAMHG37A8+d7jLzQOCbjNWW8uWvB/E9daS5qUTx0XiSZ6vhsuahH5GemuXQiWRKolkTDZzhcYoeau4VorEZb/M7pRe236qyqQx6y1XzA5NSr5uGFuzO3XrT5acXJ/AMOrUinpojs2kKdvSy9EutmfHWfrm0+G1m8z9U30rd08NvbYS64pTh6uVHO2Vlv+jLHiPPJKMub4YaH6v5HcoVk1hvU1waZ5v9S2+ZHYsbnnpLO5muk/WivRUlqUNKOnWaJVMoq5IzUm9+pAYLipVrVFSpNpbPHWci5VeNzKk5uL5+X/8ATtSpzp1VPKTWyRM7Kne1FOu02uvBvmyesd82+VyrOd3DzjjVdTkny47f7OvQrznH2iafx3NlK2o0o4pxX9IJUl2E6unMxXGKxkSpBSTT2ZbGONGRNGW3DtVK24pGD6L2PRUUqkMKWe04t+uStCqlnDydSFSKoqpTeMrODSc/lXxyqnKyyWxVTnz8si2exeXL+b1MNhJbsaGwktzTipluKyZbisiokYOIe6ZtbMPEPdMKy8N3Z2aWxxOGv1n8ztUXoEXFtPYpLqfRCKqu5X1FlYqWwF9Doi10NQ6Itco5170THT3Nl90DDS3Iq8gkArVW9w/mYTbV9w/mYM6mmST6QIifSBFZOiUQiUAwAAEjlY+SKklC5JyA6Yr3IyGdQH6imbx9SxvQpqPVfMDBxd+xOIdniz9ijjG4zQel4PLNCPyPNHf4JL2SROl59duLLEUxLYs5uiwz3TkorEml8GXoWdPztKSW+5KvPrixpuNRvsbT/wCSb64moxhDVvb5l2MTaZEqWZprVk12zGWpYKdGFSEs1V0k3qyyxtKkJxqVYrEU0lnfPadGmkkuaCyFRSmuxfAv2z/zm6yeZUMycl8EjVYZzgonHBpsFqYrrPW9rAvK39yyemoRw9g0p8xLOXqWwhjqLEmNjO5WcEdESCixuVbshhHHJVURe9CmprkK515SdSPLF41Low/6elST1bwFU02aTpqeNVsVmerFHzfKn1FlSSwY+I1JqHs+k2h6PNKkuY3y4/y39aoP1RJbsmGkRZdZXJTJ6iky3FyRUS0MF/7pm2bMF/7plGThr9Znao7HD4c/WZ26L0ILy+l0TOaKHRCKqxSi6vuyqJRfb9EW4RbarMWRcrQDl3q9Qw09zoXq9l/RzobkVcBGQyFa63uJHPyb6r9hI55pks+kQgluCKysRIqJAYCAIpiRSQJJFJAkjIEZAbOhTVeqLCmrugMXFfco452OKe5OObjNB2eCS0wcY6vBZYk0OvF59eiiWRZTFlsWcnRYW0NyksoPUDLxGj5uoqiWkiulFNZOhe0/O27XWtTm0JYWGZ6duLrSlhETloSnlCtZZh1xnq7Nmix9VZKbiOiRrsVGWmSjVhyXzKpRnHOEbE4Rg8bmedzBPDTb7EslwTRrTTxNb9ZpTTMkq0JQwk0+xrBohFOC7QLUidCtNpjZAWeMGeRdORTLITWStuabeXLboy1tzVbpeYiWRjrr5DhzPMizaJKREmbcLduni9BJMmL0EkwyrluK2D3EkRoSZgvvds2NGK+92yoycP6TOzQehw7B4k/mdmg9EKkacmm32ZlNVtqmBkvasoT0K6VRyjk0XkIvOhXbQTjsXEbLLWBN0vVL+G004se/pJQLia4V77n+jmQ6R2L+GLf+jiwfrGbG4vBvAuRZSCt1X3Ejn9Zvqv2Ejn9ZWUS3BES3BFZOmMIiUyBgyQCCpyMmITkBski5DIDEMCGBOSms9UW5M9d6oDLxP3KOQdbiXuUck3GaDdwqfLcY7TCaLKXLcxFJ69XB6ItizPReYIvicnVamPQepUiyg/WA1vVYONXi6NxJdR2DFxClz0udLWP/AAKvFyqaUso0U1kx0Xoa6MtNTm9UukuorOVuYo3VWnVzGGhoua3rNGaCy9tSxK20rqVR7cpopbaPGSqjQXLktpvllylDqMVLmerL41ktGVuK0fUK46kVe6yYRqprQzrCe5PMlrjQItbEkxU9NytyyyIpq75NdD/t4fIx1WbKelGC+Bvly/kWpiSZKegknqacTp6CyYJ6CyYVU3qKyXuK2RUSZgv37Nm2Wxz+Ie6ZYjkULrzc38zp2nEoyljJxY0028jRioPKN4xr1P6yGM5LqPEacM+sjyjrzx0iuVaS/wAmTF16m64rS/kiq24vSxjmR5GpUlN6tiJtbM1jOvqHBbylVi8SRp4jWhybo+Z2PE7izkuSb5ew7M+KV7qkm2NwjrcSuIK1evUzhW1TnyzHeXlSfs8svsvVpozW42tlc5aFVeq47GWd36jUtzOK79T3EjBnU3VH7GRz3uVBLcEyHuCKydEipkgNkExSSKkkUnIEk5IQATkMkENgSZ679ZF5mrv10Bm4j7lHLOnxD3SOYbjNBZQeK0X8SsmDxNP4lR6u2eaaNMWYrKWaKNcTlXVch6PSKkyyj0iK2dQkkpRcXs1hjZ0FCOTjzdSUJbxeC2lU6h+IU+Wcaq69GZYy7DFjvz0Wrl1Wky+isNMjlXK5MyVbiqmlGmku1sNO1TqR5cOWCV5qD55VE/kedavakvUrYXYlglWd3NPzlaWH1ZLjf7/j0FXilvSXrSivmyh8SjJZp0pSzsYbThNKD5pLL+J1aVvGMeaWy2QXP9VKNetDmk/N52S1GpxnFYqPJqSe+CmrLVoyzTSfq6YKubXTYjmytBctFY0k/WkbYv2aMkY5kbKVOcqbcYtpPqNRjvxKegknqNtoxJPU05GT0FkyU9BJMCtvUVsG9SGwqJMwX3QZtkzDfdBiI4mcNkNky3YrOjCGympLqLGyiTywiAACoDbbXHJSwYhk9MEqxqg1Oo5M22ss5wc2DxA3WekTNbjXPDWpzL5RWx0Jy0OTdT56rEK9VUfsZHPe5um/Yy+Rgb1IB7giHuCKyZE5FJyA2SUKmSRUkikgSSKSBJDAGAGerHM8stlLCMc6jlPAFfEH7NHNOjfe6RzjcZoAlprdEFR6Lhk+aijoI43B5+pg7ETlXWeLUx6L9YqRZR6RFbOojJMIym8RTb+But+GSaUqz5V2BGHzDuU6SWcnKr0J21d06ixKL1PY06VKhF+bjj4nA4xDmaqdecCxrm/rnSa5SqUFLX/wTLOBKc8T1MY7SraMOV6bGpSgkslSwyWtNQ6Tqro1eqKL4KUmubYxU5S5sRibab5VqDV7eF8DNUjq5DTqdpXOWUGaRvGhGMsXdlsVjcrCYxwbrCtKjJtMyRXYXU9Av9PQSt6F5RTlBJtbrqOXc8Ir08unia/8m7hlTNBp9TNvNodJ+x57+V5SUZQeJpp/Erk9D1dWjSqrFWCku051zwWM8uhPHwYxHAb1FbNFzZXFs/aU3jtWxlbI0iTMV70GbGzDeP1GIjjSerEbGluxGdGCyehSWTZWVAAAEBKRBdCk5U209SLBBm62eEYI6PU127M1qLripy02cpvLNd5U/wATLBZkWJXq5v2MvkYHubpP2UvkYG9TLSSUKSEMSIMghkBCJQVI2BUSBOCcCt4Fc87AM2kK5NkYbJwAsl6rMT95/Ztn0WYpdP8AsoulBVI4ZELSmnnA62LIkWMHEacYRXKjnnY4hT56OUcc1yz06fB367O7E4nBac51MRg232I9lY8FlNKdxmK/j1mevWp459GjUrS5acHJ/A7FnwVx9a4l/wDFHVoW9OhDlpwUUW5SQw1XSo06McQiooic9H2BJ5En0WBVOTcTl8Th7FP4nUSzEx8QpOVtPHVqSrz689KBROLi89RucSqdPK2MO9jPTq5ZppvmeuxllScJPQvpT5FgYsrakoliksGSVTMdBVOXVkYv00ylpgreZPQWEZS30RbGOEXGbURj1FqjoCXKhorQCYotQqWB0RXS4X0KnzRub0Zj4fHFBvtkbHotTpz48/XqIy6hoyxo9ivJKeSoteGsNJrsZzrzg9C4zKl7Ofw2NyeCcgeRvbC4tH7SHq/yWxx71+oz6NJRnFxnFST6mcXifk5b3cG7eXmp9nUTDXzqW7EZ0OI8HvuH1JefoS5P5xWUc2TNsEYozFKgBLIFtNpLXcLIrwPGrKEeVJEyh2C7LBFxKeUWU6jiVJYG5sRwRcpas+eWR6CTlqUj03gt8Znr08n7OXyMLepsb9m/kYXuYbSSKMVEk5IABkxkyEiW1EgbBDmlsVSqNkpdoA25MZLBK0JAjLDJLIAN0Vuks5LCFlvCWWAso4QRN9twi8u2uSk4x7ZaHYtfJaCw7iq38I6EVwKdu665MZb6jZZ+Scq01KouSL+p622sLa1jilTS+JpzjZFGLh/CLWwhilTSfXJ7m7CRGSMgS5aFcphKQoEt4RXU6IzeWJU2AiC9QWrBSi09msDUnrgeSyijzVWHm6koPqeBeU6PE6GJKqlo9GYUjlfx6ObsUygVSglsa3FMh0dcoLjMossgsFip4ZYoIJhFl47B1hNk46kiHFtlXErVlkI4WBYQwyzrIJSHRBbaU/O10upasrNrq20OSjCPYiyq/VSCO4tV5njsOjgMhkUlsBsk5EyTkB09CcleScgPJRnHEkmuxo49/wCTPDL1uUqPm5v/AChodVMnmA8BxfyPurSMqtpL9RTX+P8AkjzMk4tqSaa3TPsuTica8nLPialUUfNV8aTj1/MsrNj5oBfd2layuJ0K8eWcHhlBpk0ZNDbiIdbErpwkRkti5EOqATwwRIZx6TPs38jE9zX/AIP5GN7mGkoZCIujDrZUQlkfCjuLKoo6Ipc3JkFsqvYIsyIUSxACWBkKTkBiRckhUkNgQwiT0nk7w3zfNWrwTm16qfUc/glmqs/P1FmMein2np7VpTkvgFalosLQnIjepKYDZJyJkHIBnIrciGxdQptQyCXxIAELMfqK5PLKIWU0y7fUqGpz15WEJWpKpBwltI4lWlKlUcJbo9A0ZLy18/DMemtviZ6mt8dY5CWo+AcXFtNYa3GWxzdtI4gizArWEFRog0IbXWiObG+xRYsIbcrhq87IfOXyx1CWm1bxFZb2R1rS3VClh6yesmU2dt5r16nTey7DYuw6cxx6638OmknJ9RTnLyTVmuiuoTJWDZDIuQyA+QyJkMgPknJXkjmCrck5KuYnnAsyQ5Cc4spBHL43wmjfLzvKudaP4o8fxDgNW2TnTTcV1H0Fv1X8ji8c4hQpWUk8c22CeHrwKQwN5k32kGln4WRAzRGCsWBEgDA9D/g/kY3ua2/UfyMb3MKeElF5wROq2Vyy9iYxKJWXuOlghIkgZEoUlASMKSBJORSQJGpU3VqxhHdsQ6HC6OZuq1togrt2sVSpxhHRRWDbQlitH46GKkXqWGn2GWnQbBMrbT17SFJmkXZIbFyGQJJF/obIB1AiGSgCTE0JYr3AnKSETJkxQi+ElJfEllMXh5RapJ/Moz3FrGtqvVn29pgqUZ0niccfHqOwGFs0S861OrHFUc6oWcXk68ralLXlS+WhXKxpy/ykv7M/Nb/6RyJrlW2pW08PMvkdr9vovpcz/senaUKXQpRT7cZL8l/kjl21vVqwWINLrb0OnbWsKGvSn2l+CcGpJHO9WpQs5qCx1sidRLRblTfaEMsE5FDIE8wZIIAnINi5DIDNkZIyAEhkggKbJDZBABnRngvKOnKnxOabbjJKSTPdy0ieT8saOJ0Ky68xYI80QBC3KVJBLwRkrNBDJFYSu9zeq/kZXuZf19XGOWH0Yn6up2RJhrdklMwfq6nZEn9ZU7I/QYa35Jyc/wDWVP4x+hP62p/GH0GGuhkk5366r/GH0ZP66r/GH0ZMproobJzP19X+MPow/X1f4w+jGU108k5OX+vq/wAYfRk/uFX+MPox8011Irnkord6HdtqahTjFbJHkKfE61OamoU212p/c1x8pLyO1Kh4X9x81ZY9jAtWx4xeVN8v9Vv4Zfcf0sv+5tvDL7k+av1HuaU8wS60OeEj5XX8XlUbbwy+4/plxHubXwy/IvzT6j3KZOTwvplxHubXwy/IPTPiPc2vhl+Qyn1HvCUeD9M+I9za+GX5B6acS7m18MvyGU+o93nLBs8IvLTiK/02vhl+QemnEe5tfDL8hifUe5fzF6zw/pnxHubXwy/IPTLiPc2vhl+RcPqPcPcg8P6Y8Q7m18MvyJ9MuI9za+GX5DDY9uic6nhvTLiPc2vhl+RPplxHubXwy/IYbHu41NNdSxST2PAemXEe5tfDL8g9MuI9za+GX5DDY+gEYPAry04kv9Vt4ZfkT6a8T7q18EvyGJse9wGx4H014l3Vr4ZfkR6Z8R7m18MvyGGvfOaXxElNv4HhPTPiPc2vhl+QemXEe5tfDL8hhse40I1PD+mXEe5tfDL8g9MeI9zbeGX5DF17kPmeG9MeI9za+GX5B6Y8Q7m18MvyGGvcZIPEemPEO5tfDL8g9MeIdza+GX5DDXt8hlniPTHiHc2vhl+RHphxDubXwy/IYa9wCPD+mHEO5tvDL8g9MOIdza+GX5DDY9u2Ge08R6YcQ7m18MvyD0w4h3Nt4ZfkMPqPbZBnifS/iHc23hl+Qel/EO5tvDL8hh9R7SWxxfKil53hEpY1pyUjiPyv4g/9Nt4ZfkUXXlJeXVtOhUpUFCaw2ovP/Iw+o5WSBQKmpAgCpqSAAIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA//2Q==\n", "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import YouTubeVideo\n", "YouTubeVideo(\"FSRoqXw28RI\",width=800, height=450)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> **_Reading_**: [Chapter 9 of the NS book.](http://networksciencebook.com/chapter/9). You can skip sections 9.3, 9.5 and 9.7. \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Exercise 3: Zachary's karate club__: In this exercise, we will work on Zarachy's karate club graph (refer to the Introduction of Chapter 9). The dataset is available in NetworkX, by calling the function [karate_club_graph](https://networkx.org/documentation/stable//auto_examples/graph/plot_karate_club.html) \n", ">\n", "> 1. Visualize the graph. Set the color of each node based on the club split (the information is stored as a node attribute). My version of the visualization is below.\n", ">\n", "> 2. Write a function to compute the __modularity__ of a graph partitioning (use **equation 9.12** in the book). The function should take a networkX Graph and a partitioning as inputs and return the modularity.\n", "> 3. Explain in your own words the concept of _modularity_. \n", "> 4. Compute the modularity of the Karate club split partitioning using the function you just wrote. Note: the Karate club split partitioning is avilable as a [node attribute](https://networkx.org/documentation/networkx-1.10/reference/generated/networkx.classes.function.get_node_attributes.html), called _\"club\"_.\n", "> 5. Create $1000$ randomized version of the Karate Club network using the _double edge swap_ algorithm you wrote in the exercise above 5. For each of them, compute the modularity of the \"club\" split and store it in a list.\n", "> 6. Compute the average and standard deviation of the modularity for the random network.\n", "> 7. Plot the distribution of the \"random\" modularity. Plot the actual modularity of the club split as a vertical line (use [axvline](https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.axvline.html)). \n", "> 8. Comment on the figure. Is the club split a good partitioning? Why do you think I asked you to perform a randomization experiment? What is the reason why we preserved the nodes degree?\n", "> 9. Use [the Python Louvain-algorithm implementation](https://anaconda.org/auto/python-louvain) to find communities in this graph. Report the value of modularity found by the algorithm. Is it higher or lower than what you found above for the club split? What does this comparison reveal?\n", "> 10. Compare the communities found by the Louvain algorithm with the club split partitioning by creating a matrix **_D_** with dimension (2 times _A_), where _A_ is the number of communities found by Louvain. We set entry _D_(_i_,_j_) to be the number of nodes that community _i_ has in common with group split _j_. The matrix **_D_** is what we call a [**confusion matrix**](https://en.wikipedia.org/wiki/Confusion_matrix). Use the confusion matrix to explain how well the communities you've detected correspond to the club split partitioning." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\"Drawing\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Exercise 4__: Community detection on the network of Computational Social Scientists. \n", ">\n", "> * Consider the network of Computational Social Scientists. \n", "> * Use [the Python Louvain-algorithm implementation](https://anaconda.org/auto/python-louvain) to find communities. How many communities do you find? What are their sizes? Report the value of modularity found by the algorithm. Is the modularity significantly different than 0? \n", "> * If you are curious, you can also try the *Infomap* algorithm. Go to [this page]. (https://mapequation.github.io/infomap/python/). It's harder to install, but a better community detection algorithm. You can read about it in [advanced topics 9B](http://networksciencebook.com/chapter/9#advanced-9b).\n", "> * Visualize the network, using netwulf (see Week 5). This time assign each node a different color based on their _community_. Describe the structure you observe.\n", "> * Make sure you save the assignment of authors to communities.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.7" } }, "nbformat": 4, "nbformat_minor": 2 }