kshell_moified.ipynb · Xinli_Shi/Top-k influence node acquisition in a complex network model

forked from Secure_DisOpt&Cont/Top-k influence node acquisition in a complex network model

加入 Gitee

与超过 1200万开发者一起发现、参与优秀开源项目，私有仓库也完全免费：）

克隆/下载

kshell_moified.ipynb 5.18 KB

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "714d700c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "from numpy import *\n",
    "import math\n",
    "import random\n",
    "import time\n",
    "\n",
    "def Compute_Degree(G):\n",
    "    #将G.degree()的返回值变为字典\n",
    "    node_to_degree = {}\n",
    "    for item in G.degree():\n",
    "        node_to_degree[item[0]]=item[1]\n",
    "    return node_to_degree\n",
    "\n",
    "def k_shell(G):\n",
    "    #返回一个key为核数，value为节点的dict\n",
    "    newG=G.copy()\n",
    "    core_to_node={}\n",
    "    now_ks=1\n",
    "    while len(newG.degree):\n",
    "        core_to_node[now_ks]=[]\n",
    "        while True:\n",
    "            level_node_list=[]\n",
    "            for item in newG.degree:\n",
    "                if item[1]<=now_ks:\n",
    "                    level_node_list.append(item[0])\n",
    "            newG.remove_nodes_from(level_node_list)\n",
    "            core_to_node[now_ks].extend(level_node_list)\n",
    "            if not len(newG.degree):\n",
    "                return core_to_node\n",
    "            if min(newG.degree, key=lambda x:x[1])[1]>now_ks:\n",
    "                break\n",
    "        now_ks=min(newG.degree, key=lambda x:x[1])[1]\n",
    "    return core_to_node\n",
    "\n",
    "def sumDegree(G):\n",
    "    \"\"\"\n",
    "    计算G中度的和\n",
    "    \"\"\"\n",
    "    G_degrees = Compute_Degree(G)\n",
    "    sum = 0\n",
    "    for v in G_degrees.values():\n",
    "        sum += v\n",
    "    return sum\n",
    "\n",
    "\n",
    "def degree_norm(G):\n",
    "    \"\"\"\n",
    "    归一化\n",
    "    \"\"\"\n",
    "    sum = sumDegree(G)\n",
    "    I = {}\n",
    "    G_degrees = Compute_Degree(G)\n",
    "    for k, v in G_degrees.items():\n",
    "        I[k] = v / sum\n",
    "    return I\n",
    "\n",
    "\n",
    "def Entropy(G):\n",
    "    \"\"\"\n",
    "    Entropy(G) 计算出G中所有节点的熵\n",
    "    I 为重要性\n",
    "    e 为节点的熵sum += I[i]*math.log(I[i])\n",
    "    \"\"\"\n",
    "    I = degree_norm(G)\n",
    "    ent_of_G = {}\n",
    "    for k, v in I.items():\n",
    "        sum = 0\n",
    "        for i in G.neighbors(k):\n",
    "            sum += I[i] * math.log(I[i])\n",
    "        sum = -sum\n",
    "        ent_of_G[k] = sum\n",
    "    return ent_of_G\n",
    "\n",
    "\n",
    "def kshellEntropy(G):\n",
    "\n",
    "    # 计算所有壳层下，所有节点的熵值，返回字典，key是核数，value是一个字典，代表节点及其对应熵值\n",
    "\n",
    "    ks = k_shell(G)\n",
    "    ent_of_G = Entropy(G)\n",
    "    kshell_ent = {}\n",
    "    new_ks = sorted(ks.keys(), reverse=True)\n",
    "    for ksI in new_ks:\n",
    "        ksE = {}\n",
    "        for i in ks[ksI]:\n",
    "            ksE[i] = ent_of_G[i]\n",
    "        kshell_ent[ksI] = ksE\n",
    "    return kshell_ent\n",
    "\n",
    "\n",
    "def kshellEntropySort(G):\n",
    "    #排序\n",
    "    k_shell_Ent = kshellEntropy(G)\n",
    "    k_shell_ans = []\n",
    "    sorted_ksEnt = sorted(k_shell_Ent.keys(), reverse=True)\n",
    "    for item in sorted_ksEnt:\n",
    "        t = sorted([(v, k) for k, v in k_shell_Ent[item].items()], reverse=True)\n",
    "\n",
    "        # 熵值相同的节点放在一个set里面\n",
    "        t_new = {}\n",
    "        for item in t:\n",
    "            t_new.setdefault(item[0], list()).append(item[1])\n",
    "        # 按熵值排序变成列表\n",
    "        t = sorted([(k, v) for k, v in t_new.items()], reverse=True)\n",
    "\n",
    "        # 把相同熵值的节点列表打乱顺序随机选择\n",
    "        sub_ksES = []\n",
    "        for item in t:\n",
    "            if len(item[1]) == 1:\n",
    "                sub_ksES += item[1]\n",
    "            else:\n",
    "                random.shuffle(item[1])\n",
    "                sub_ksES += item[1]\n",
    "\n",
    "        k_shell_ans.append(sub_ksES)\n",
    "    return k_shell_ans\n",
    "\n",
    "\n",
    "def get_top_nodes(G):\n",
    "    starttime = time.time()\n",
    "    top_nodes = []\n",
    "    node_rank = kshellEntropySort(G)\n",
    "    while (len(node_rank) != 0):\n",
    "        for i in range(len(node_rank)):\n",
    "            top_nodes.append(node_rank[i].pop(0))\n",
    "        while True:\n",
    "            if [] in node_rank:\n",
    "                node_rank.remove([])\n",
    "            else:\n",
    "                break\n",
    "    endtime = time.time()\n",
    "    print('改进的基于信息熵的k_shell算法： %f second' % (endtime - starttime))\n",
    "    return top_nodes\n",
    "\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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

一键复制编辑原始数据按行查看历史

提交于 2023-03-24 02:43 . first commit

马建仓 AI 助手

尝试更多

代码解读

代码找茬

代码优化

Python

https://gitee.com/xinli-shi/top-k-influence-node-acquisition-in-a-complex-network-model.git

git@gitee.com:xinli-shi/top-k-influence-node-acquisition-in-a-complex-network-model.git

xinli-shi

top-k-influence-node-acquisition-in-a-complex-network-model

Top-k influence node acquisition in a complex network model

master

Xinli_Shi/Top-k influence node acquisition in a complex network model

简介

发行版

贡献者

近期动态

Xinli_Shi/Top-k influence node acquisition in a complex network model .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

Xinli_Shi/Top-k influence node acquisition in a complex network model