mirea-projects/Second term/Discrete math/Задание_11.ipynb

380 lines
48 KiB
Plaintext
Raw Permalink Normal View History

2024-09-23 23:22:33 +00:00
{
"cells": [
{
"cell_type": "markdown",
"id": "6059efcd",
"metadata": {},
"source": [
"# Графы"
]
},
{
"cell_type": "markdown",
"id": "2bb2048b",
"metadata": {},
"source": [
"## Связность и разреженность графов. "
]
},
{
"cell_type": "markdown",
"id": "dbe8a4df",
"metadata": {},
"source": [
"\n",
"![title](images/Снимок_экрана1.jpg)\n"
]
},
{
"cell_type": "markdown",
"id": "9b3416ff",
"metadata": {},
"source": [
"## Гигантсткие компоненты"
]
},
{
"cell_type": "markdown",
"id": "328b16c7",
"metadata": {},
"source": [
"\n",
"![title](images/Снимок_экрана2.jpg)\n"
]
},
{
"cell_type": "markdown",
"id": "fd5b6604",
"metadata": {},
"source": [
"## Диаметр сложных сетей"
]
},
{
"cell_type": "markdown",
"id": "dff99fcf",
"metadata": {},
"source": [
"\n",
"![title](images/Снимок_экрана3.jpg)\n"
]
},
{
"cell_type": "markdown",
"id": "34c62bab",
"metadata": {},
"source": [
"## Устойчивость гигантской компоненты"
]
},
{
"cell_type": "markdown",
"id": "b5bb7b77",
"metadata": {},
"source": [
"\n",
"![title](images/Снимок_экрана4.jpg)\n",
"\n",
"![title](images/Снимок_экрана4_1.jpg)\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "700c5810",
"metadata": {},
"source": [
"## Устойчивость к атакам на хабы"
]
},
{
"cell_type": "markdown",
"id": "31179960",
"metadata": {},
"source": [
"\n",
"![title](images/Снимок_экрана5.jpg)\n",
"\n",
"![title](images/Снимок_экрана5_2.jpg)\n",
"\n",
"![title](images/Снимок_экрана5_3.jpg)\n"
]
},
{
"cell_type": "markdown",
"id": "211e44bf",
"metadata": {},
"source": [
"## Степенной закон распределения вершин"
]
},
{
"cell_type": "markdown",
"id": "824edd9a",
"metadata": {},
"source": [
"\n",
"![title](images/Снимок_экрана6.jpg)\n"
]
},
{
"cell_type": "markdown",
"id": "42640b23",
"metadata": {},
"source": [
"## Задачи"
]
},
{
"cell_type": "markdown",
"id": "21d8b493",
"metadata": {},
"source": [
"### Задача 1. Рассмотрим модель случайных графов на n вершинах, в котором каждое из возможных ребер проводится независимо от всех остальных с с одной и той же вероятностью. Используя библиотеку NetworkX, сгегенрируйте граф на 1000 вершинах при р=0,003. Оцените разницу между количеством ребер и их ожидаемым количеством. Постройте график распределения вершин в log-log координатах. Оцените степенную зависимость закона распределения вершин. "
]
},
{
"cell_type": "code",
"execution_count": 26,
"id": "cc065936",
"metadata": {},
"outputs": [],
"source": [
"import networkx as nx\n",
"import matplotlib\n",
"matplotlib.rcParams['xtick.labelsize'] = 18\n",
"matplotlib.rcParams['ytick.labelsize'] = 18\n",
"import matplotlib.pyplot as plt\n",
"import pylab\n",
"%matplotlib inline\n",
"pylab.rcParams['figure.figsize'] = 10, 10"
]
},
{
"cell_type": "code",
"execution_count": 27,
"id": "9dfe4c39",
"metadata": {},
"outputs": [],
"source": [
"G = nx.gnp_random_graph(1000, 0.003)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"id": "2d19ab3c",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ожидаемое количество рёбер: 1498\n",
"Колличество рёбер в графе: 1540\n"
]
}
],
"source": [
"## ваш код здесь для подсчета количества сгенерированных ребер и ожидаемого их количества\n",
"import itertools\n",
"\n",
"x = G.nodes()\n",
"number_of_nodes = len(list(itertools.combinations(x, 2)))\n",
"print(\"Ожидаемое количество рёбер:\", round(0.003 * number_of_nodes))\n",
"print(\"Колличество рёбер в графе: \", G.number_of_edges())"
]
},
{
"cell_type": "code",
"execution_count": 29,
"id": "7b3aaf8c",
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAA20AAANzCAYAAAA6LvAhAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjkuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy80BEi2AAAACXBIWXMAAA9hAAAPYQGoP6dpAABxAklEQVR4nO3deXxU1f3/8fedhARiMpMF2RUQFWRREeJSviARFUGDoGxugCioVYuFr1a/LoBSrRVR+zNqrQjBBUvYxLogogiluCD4VSyiXyVsYQ/ZCFnn/P6YzpiYbTJZ5ibzej4eeUzm3nPv+dwJ7WPennvPsYwxRgAAAAAAW3IEuwAAAAAAQNUIbQAAAABgY4Q2AAAAALAxQhsAAAAA2BihDQAAAABsjNAGAAAAADZGaAMAAAAAGyO0AQAAAICNEdoAAAAAwMYIbQAA1JOFCxfKsix16dKlwr5Zs2bJsiwNHjy40evyx7p162RZlizLqrCvuuuyk8GDB8uyLM2aNSvYpQBAvSK0AYCNeb/ol/1xOBxyOp3q1KmTfvOb3+jOO+/U0qVLVVRUFOxy0YjWrVunWbNmaeHChcEupcGtXLlSs2bN0sqVK4NdCgAEBaENAJqItm3bqm3btmrTpo0sy1JGRoY2bdqkF154QWPGjFGHDh300ksvBbtMVKF169bq3r27Tj311Ho537p16zR79ux6C21RUVHq3r27unfvXi/nq08rV67U7Nmzawxtp556qrp3767WrVs3TmEA0EjCg10AAMA/Bw4cKPe+tLRU//73v7VmzRo9//zz2rlzp+644w5t2LBBr7/+eqW3uSF47rrrLt11113BLqNK559/vr7//vtgl1EnixYtCnYJANAgGGkDgCYqLCxMffr00fTp07Vt2zaNHz9ekvTmm2/qT3/6U5CrAwAA9YXQBgDNQFRUlFJTU9W3b19J0p/+9CdlZmZW2raoqEgvvPCCkpKS1Lp1a0VERKhdu3a6+uqr9f7771fbz/HjxzVz5kydddZZatWqldq0aaPhw4dr7dq1kqQuXbrIsqwKt+ylp6f7nslLT0/XTz/9pKlTp6pr166KjIysMMGF2+3WG2+8oeHDh6tt27aKiIjQySefrMsvv1yLFy+WMabaOrdt26apU6fqjDPOUFRUlKKjo3X22WfrwQcf1JEjR6o9tiafffaZRo4cqdatW6tVq1bq3r27HnzwQeXl5VV7XE0TkaxevVrXXHONOnXqpIiICDmdTp122mm6/PLLNXfuXN/f0/tZzp49W5L06aefVnjuseznX3ZyjuLiYj399NPq37+/YmNjZVmW1q1bJ6n6iUh+bc2aNRo2bJhOPvlktWrVSr169dKcOXNUUFBQaftJkybJsixNmjSpynNWNtmJt6bU1FRJUmpqaoVr9db/62utyvLly3XVVVf5/l21bdtWV111lVasWFHlMb+uf+nSpRo8eLDi4+MVFRWlc889V88995zcbneV5wCAOjEAANuaOXOmkWT8/b/rtLQ0X/v58+dX2J+enm569erla2NZlnG5XL73ksztt99e6bkPHjxoevbs6WvXokULExsb6zvPiy++aDp37mwkmQULFpQ7dufOnb7j3njjDRMdHW0kmaioKHPSSSeZzp07+9oePXrUDBo0qFxNv65xxIgRprCwsNI6n3zySeNwOHxto6KiTEREhO99+/btzZYtW/z6PH9t/vz55c7tcrl85+7Ro4eZN2+ekVTuery8f8uLL764wr7Zs2eXu76oqCjfZ+T9+eSTT4wxxuzevdu0bdvWnHTSSb6/Q9u2bcv9vPXWW75zX3zxxUaS+cMf/mB+85vfGEkmPDzcxMXFGcuyfOf95JNPqvy3tmDBAt91paSkGMuyjCQTGxtrwsPDfcf17dvXZGZmVjh+4sSJRpKZOHFilZ9t2T68Nm7caNq2bWtatmxpJJmWLVtWuNaNGzdWuNaZM2dWOH9hYaEZN26cr1aHw2Hi4uLK/T2vu+46U1RUVG39d955p+94779/78+ECROqvD4AqAtCGwDYWG1DW25urgkLC6v0C2ReXp7p0aOHkWQGDx5s1q1bZwoKCowxxmRlZZl58+b5gsKzzz5b4dxXXHGFkWRatWpl5s+f7zt29+7dZty4cSYiIsJERUXVGNqio6PNBRdcYL788kvf/h07dhhjjCkpKfF98T733HPNO++8Y44fP+6rPzU11bRp08ZIMvfcc0+FGl955RVfH3/84x/N/v37fefdvHmzueSSS4wk06lTJ5Obm+vXZ+r11Vdf+QLK4MGDzfbt240xxhQVFZnFixeb2NhY35f42oS29PR0X3CYPn262bdvn29fVlaW2bBhg/ntb39rNm/e7Nf5fs37eUZHR5vo6GizYMECk5+fb4wx5siRI+bo0aPGGP9CW1RUlGnRooUZM2aM2b17tzHGmPz8fPPiiy+ayMhII8mMGjWqwvGBhrbaHF/2WisLbTNmzPD9B4aHH37YHDt2zBhjTGZmpvmf//kf37X/4Q9/qLL/uLg4ExERYebNm2eys7ONMZ7P8NZbb/Udv3bt2mprBIBAENoAwMZqG9qMMeaMM84wksyAAQPKbX/00Ud9X/IrG00wxpjly5cbSaZ169amuLjYt33Dhg2+Ol577bUKx5WWlpqkpCRfm+pCW+fOnasMTIsWLfKNWmVlZVXaZvPmzcayLBMREWEOHjzo256Tk+MLTR988EGlxxYXF5t+/foZSeaZZ56ptE1Vhg0bZiSZM8880xd6yvrggw/KXeOvVRWy/v73v/vOWxu1DW2SzKpVq6ps509o8/ZXWlpaoY03MEsyX3zxRbl9wQ5te/fu9QXuBx54oNJjp0+f7hu5zMjIqLT/yv5te3n/Xd16663V1ggAgeCZNgBoZuLj4yWpwjNt8+fPlyRNnz5dLVq0qPTYkSNHyul06siRI/rqq69829PS0iR5nlm74YYbKhzncDj00EMP+VXfXXfdpejo6Er3eWu844475HK5Km3Tr18/9erVS0VFRfrkk09825ctW6asrCz17dtXQ4cOrfTY8PBwXXfddZI8z5D5Kysry9f+3nvvVatWrSq0GTp0qC666CK/z+kVGxsrScrNzdXx48drfby/evXqpeTk5Dqf56GHHpLDUfHrw80336xOnTpJkt56660691Ofli1bppKSErVs2VL3339/pW0eeughRUZGqri4WEuXLq20zSmnnKKJEydWum/EiBGSpG+++aZ+igaAMpjyHwBCwL59+7Rr1y5J0i233KKwsLAq23on1Ni1a5cuuOACSdKWLVskSYMGDapyoooBAwYoPDxcJSUl1dYyYMCASreXlpbqs88+k+SZtOPxxx+v8hzeQOq9JknauHGjJGn79u1q165dlceeOHGiwrE12bJli2+SiUsuuaTKdpdccok2bdrk93klz1T7rVu31v79+3XBBRfo9ttv16WXXqru3bvX67INVX3utREeHq6BAwdWus/hcGjw4MF6/fXXtXnz5jr3VZ+89SQmJsrpdFbaJi4uTv3799fGjRurrD8xMbHKv0mHDh0kVfyPJQBQHwhtANDMeL80JiQk+LZlZGT4fvd39sT8/Hzf74cPH5b0yxfTykRGRqp169YV1pP7tTZt2lS6PTMzU4WFhZKkY8eO1bpG7zUWFBRUOYthVcfW5NChQ77fO3bsWGU770hTbcTGxmrx4sW6/vrr9d133+nuu++WJLlcLg0aNEhjx47VuHHjqhwd9VdVn3tttG7dWpGRkVXu9342ZT8vO/DWU93fTvrl71dV/TExMVUeGx7u+UpVXFwcSIkAUC1ujwSAZiQvL08///yzJKlbt26+7aWlpb7ft2/fLuN5prnan8qmZ6+PkZ+qRvnK1vj+++/7VWPZqd29x48bN86vY9PT0+t8LfXl0ksv1c6dO7Vo0SJNnDhRZ5xxhrKzs/XOO+/opptuUt++fbVv37469VHd6CoAwN4IbQDQjHzwwQe+8FJ2PbCytwvW5rZAr5NPPllS+RG7XyssLKzTGmgJCQm+0YpAavReYyDH1qTsKFV14akuweqkk07STTfdpIU
"text/plain": [
"<Figure size 1000x1000 with 1 Axes>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# подсчет количества вершин каждой степени\n",
"degrees = dict()\n",
"for degree in dict(G.degree()).values():\n",
" if degree in degrees:\n",
" degrees[degree] += 1\n",
" else:\n",
" degrees[degree] = 1\n",
"# Ваш код для формирования такого же словаря, с помощью библиотечных функций\n",
"\n",
"\n",
"sorted_degree_values = sorted(degrees.keys())\n",
"counts = [degrees[d] for d in sorted_degree_values]\n",
"plt.loglog(sorted_degree_values, counts, ls='None', marker='o', color='r', markersize=8)\n",
"plt.xlabel(\"degree (log)\", fontsize=18)\n",
"plt.ylabel(\"number of vertices (log)\", fontsize=18)\n",
"plt.title(\"Degree distribution\", fontsize=18)\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "f2b1060f",
"metadata": {},
"source": [
"### Задача 2. Найдите число компонено связности в графе из предыдущей задачи. Есть ли в нем гигантская уомпонента? Сколько в ней вершин, каков ее диаметр? Удажите из графа 10- ую часть вершин. Остентся ли в графе гигантская компонента? Сделайте исследование при какой доле вершин гигантская компонента разрушается."
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "24ccb3b0",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"46\n",
"Graph with 950 nodes and 1535 edges\n",
"13\n"
]
}
],
"source": [
"components = nx.number_connected_components(G)\n",
"print (components)\n",
"giant_component_list = sorted(nx.connected_components(G), key=len, reverse=True) # reverse для сортировки по убыванию\n",
"giant_component = G.subgraph(giant_component_list[0])\n",
"print (G.subgraph(giant_component))\n",
"# print(len(max(nx.connected_components(G), key=len))) # количество вершин в гигантской компоненте\n",
"print (nx.diameter(giant_component))\n"
]
},
{
"cell_type": "code",
"execution_count": 31,
"id": "172d4d3f",
"metadata": {},
"outputs": [],
"source": [
"# Ваш код здесь для удаления 10 процентов случайных вершин\n",
"import random\n",
"\n",
"H = G.copy()\n",
"for node in list(H.nodes()):\n",
" if random.random() < 0.1:\n",
" H.remove_node(node)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"id": "7af62d1b",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"895\n",
"57\n",
"831\n"
]
}
],
"source": [
"# вывести количество оставшихся вершин, количество компонент связности, гигантскую компоненту связности\n",
"comps = list(nx.connected_components(H))\n",
"print(H.order())\n",
"print(len(comps))\n",
"print(len(comps[0]))"
]
},
{
"cell_type": "markdown",
"id": "87d38664",
"metadata": {},
"source": [
"### Задача 3. Найдите число компонено связности в графе из предыдущей задачи. Есть ли в нем гигантская уомпонента? Сколько в ней вершин, каков ее диаметр? Удажите из графа 50 самых больших по степени вершин. Остентся ли в графе гигантская компонента? Сделайте исследование при какой доле вершин гигантская компонента разрушается."
]
},
{
"cell_type": "code",
"execution_count": 33,
"id": "2380c355",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"900\n",
"774\n"
]
}
],
"source": [
"# Ваш код здесь для удаления 50 вершин-хабов\n",
"H = G.copy()\n",
"nodes = sorted(H.nodes(), key=lambda v: H.degree(v), reverse=True)\n",
"for node in nodes[:100]:\n",
" H.remove_node(node)\n",
"\n",
"print(H.order())\n",
"print(len(next(nx.connected_components(H))))"
]
},
{
"cell_type": "code",
"execution_count": 34,
"id": "b8228d0a",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"900\n",
"105\n",
"774\n"
]
}
],
"source": [
"# вывести количество оставшихся вершин, количество компонент связности, гигантскую компоненту связности\n",
"comps = list(nx.connected_components(H))\n",
"print(H.order())\n",
"print(len(comps))\n",
"print(len(comps[0]))"
]
}
],
"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.11.0"
}
},
"nbformat": 4,
"nbformat_minor": 5
}