Memorial Sea

摘要#

• 本文章是基于个人对k-shell算法的理解，若有偏颇还望指正。
• 基于java实现的k-shell算法，文末附源码，仅供学习。

k-shell算法#

• 从数据结构图中逐步删除节点权值小于某阈值的节点以及其相关路径的算法

• K-shell 方法递归地剥离网络中度数小于或等于 k 的节点,具体划分过程如下: 假设网络中不存在度数为 0 的孤立节点。从度指标的角度分析,度数为 1的节点是网络中最不重要的节点,因此首先将度数为 1 的节点及其连边从网络中删除。删除操作进行之后的网络中会出现新的度数为 1 的节点,接着将这些新出现的度数为 1 的节点及其连边删除。重复上述操作,直到网络中不再新出现度数为 1的节点为止。此时所有被删除的节点构成第一层,即 1-shell,节点的 Ks 值等于 1。剩下的网络中,每个节点的度数至少为2。继续重复上述删除操作,得到 Ks 值等于 2 的第二层,即 2-shell。依此类推,直到网络中所有的节点都被赋予 Ks 值。 出处

• 关于k-shell算法的一些小问题，目前为止本人未能找到足够官方的文章讲解。若有人能指正，感激不尽。

  节点的度在图的定义中可以理解为节点与其他节点的路径数目。在我们删除对应度数节点的过程中势必会又节点度数更大的节点变为度数小的节点。这样节点的度数就会改变，对于这种改变发生而产生的低于当前处理度数k的新节点又应该怎样处理？

  本代码对这类节点，这个代码处理时在删除当前所有节点度数小于等于ks值的节点，并把删除节点加入ks值。针对此次提供的数据ks层数最大值为12。实验数据以及实验结果将会附在源代码末尾

数据结构安排#

以下代码使用vscode+java环境编写

• 因为是使用的java语言。这里用一个hashmap来存储图。hashmap中key，value分别为string，以及hashset。 key值中存储图节点，对应value（hashset型）存储与该节点有连接的节点。

  1
  HashMap<String,HashSet<String>> map=new HashMap<String,HashSet<String>>();

• 用另一个hashmap来存储对应k值的网络层,key值用来存放k值，value的hashset里面存放从网络中剔除的节点。

  1
  HashMap<Integer,HashSet<String>> kmap=new HashMap<Integer,HashSet<String>>();

• 首先第一步从文件中读取数据,这里操作时按行读取。java文件操作

  1
  private static void loadfile(String filename){
  2
      map.clear();                                                //将图清空重置
  3
      try {
  4
          File f=new File(filename);                              //尝试打开文件
  5
          FileInputStream fstream=new FileInputStream(f);
  6
          InputStreamReader ireader=new InputStreamReader(fstream);
  7
          BufferedReader breader=new BufferedReader(ireader);
  8
          String line=""; //存储每一行的数据
  9
          String a="";    //存储逗号左边
  10
          String b="";    //存储逗号右边
  11
          String[] points;//存储行数据分割之后的内容
  12
          HashSet<String> temp=null;
  13
  
  14
          while ((line=breader.readLine())!=null){
  15
              points=line.split(","); //以逗号分割字符串
  16
              a=points[0];
  17
              b=points[1];
  18
              temp=map.get(a);
  19
              if (temp!=null){    //这里的读取操作有点绕
  20
                  temp.add(b);    //将逗号前面的节点当作key值在map中检索，如果存在对应的value
  21
              }                   //就把逗号后面的节点存入这个key值所对应的value中
  22
              else{               //如果不存在，证明map中还没有这个节点的信息。
  23
                  temp=new HashSet<String>();
  24
                  temp.add(b);    //则将逗号前面的节点作为key
  25
                  map.put(a, temp);   //逗号后面的节点作为value中的元素存入map中
  26
              }
  27
  
  28
              temp=map.get(b);    //这里将逗号前后对换位置重复一遍，保证map的key值中包含所有的节点
  29
              if (temp!=null){
  30
                  temp.add(a);
  31
              }
  32
              else{
  33
                  temp=new HashSet<String>();
  34
                  temp.add(a);
  35
                  map.put(b, temp);
  36
              }
  37
          }
  38
          breader.close();
  39
      } catch (Exception e) {
  40
          //TODO: handle exception
  41
          e.printStackTrace();
  42
      }
  43
  
  44
  }

• 为了方便查看图的变化这里写了一个map的打印函数：

  1
  private static void mapprint(){
  2
      Iterator iter=map.entrySet().iterator();
  3
      while (iter.hasNext()){
  4
          Map.Entry<String,HashSet<String>> entry=(Map.Entry<String,HashSet<String>>) iter.next();
  5
          System.out.println(entry.getKey()+" "+entry.getValue().toString());
  6
      }
  7
  }

• 以及存储对应k值剥离出来的网络节点的打印函数

  1
  private static void printkmap(){
  2
      Iterator iter=kmap.entrySet().iterator();
  3
      while(iter.hasNext()){
  4
          Map.Entry<Integer,HashSet<String>> entry=(Map.Entry<Integer,HashSet<String>>) iter.next();
  5
          System.out.println(entry.getKey().toString()+" "+entry.getValue().toString());
  6
      }
  7
  }

• k-shell算法。

  • 以图（hashmap为空为终止条件）为空为终止条件的循环。每次删除节点权值小于k的节点以及相应路径，在图（hashmap）一轮遍历完成之后k值+1。
  • 删除的时候要注意，这样的存储结构的设计模式，我们删除一个节点时，要同时把该节点从其他与该节点相连接的节点的value中删除。因此这里的删除函数显得很复杂。

  Hashmap的遍历删除操作

  1
  private static void kshell_func(){
  2
      int k=1;
  3
      kmap.clear();
  4
      while (!map.isEmpty()){
  5
          HashSet<String> ktemp=new HashSet<String>();
  6
          for (Iterator<Map.Entry<String,HashSet<String>>> iter = map.entrySet().iterator(); iter.hasNext();){
  7
              Map.Entry<String,HashSet<String>> item = iter.next();
  8
              if (item.getValue().size()<=k){
  9
                  ktemp.add(item.getKey())
  10
                  for (String i:item.getValue()){
  11
                      HashSet<String> temp=map.get(i);
  12
                      temp.remove(item.getKey());
  13
                  }
  14
                  iter.remove();
  15
              }
  16
          }
  17
  
  18
          // Iterator iter=map.entrySet().iterator();
  19
          // Map.Entry<String,HashSet<String>> entry=(Map.Entry<String,HashSet<String>>) iter.next();
  20
          // while (iter.hasNext()){
  21
          //     if (entry.getValue().size()<=k){
  22
          //         ktemp.add(entry.getKey());
  23
          //         for (String index:entry.getValue()){
  24
          //             HashSet<String> temp=map.get(index);
  25
          //             temp.remove(entry.getKey());
  26
          //         }
  27
          //         String keytemp=entry.getKey();
  28
          //         entry=(Map.Entry<String,HashSet<String>>) iter.next();
  29
          //         map.remove(keytemp);
  30
          //         System.out.println("delete ...");
  31
          //     }
  32
          // }
  33
          kmap.put(Integer.valueOf(k),ktemp);
  34
          k=k+1;
  35
      }
  36
  }

源码#

数据文件

结果文件

1
import java.io.BufferedReader;
2
import java.io.File;
3
import java.io.FileInputStream;
4
import java.io.InputStreamReader;
5
import java.util.HashMap;
6
import java.util.HashSet;
7
import java.util.Iterator;
8
import java.util.Map;
9
import java.lang.Integer;
10

11
public class kshell{
12
    private static HashMap<String,HashSet<String>> map=new HashMap<String,HashSet<String>>();
13
    private static HashMap<Integer,HashSet<String>> kmap=new HashMap<Integer,HashSet<String>>();
14
    private static void loadfile(String filename){
15
        map.clear();
16
        try {
17
            File f=new File(filename);
18
            FileInputStream fstream=new FileInputStream(f);
19
            InputStreamReader ireader=new InputStreamReader(fstream);
20
            BufferedReader breader=new BufferedReader(ireader);
21
            String line="";
22
            String a="";
23
            String b="";
24
            String[] points;
25
            HashSet<String> temp=null;
26

27
            while ((line=breader.readLine())!=null){
28
                points=line.split(",");
29
                a=points[0];
30
                b=points[1];
31
                temp=map.get(a);
32
                if (temp!=null){
33
                    temp.add(b);
34
                }
35
                else{
36
                    temp=new HashSet<String>();
37
                    temp.add(b);
38
                    map.put(a, temp);
39
                }
40
                temp=map.get(b);
41
                if (temp!=null){
42
                    temp.add(a);
43
                }
44
                else{
45
                    temp=new HashSet<String>();
46
                    temp.add(a);
47
                    map.put(b, temp);
48
                }
49
            }
50
            breader.close();
51
        } catch (Exception e) {
52
            //TODO: handle exception
53
            e.printStackTrace();
54
        }
55

56
    }
57

58
    private static void mapprint(){
59
        Iterator iter=map.entrySet().iterator();
60
        while (iter.hasNext()){
61
            Map.Entry<String,HashSet<String>> entry=(Map.Entry<String,HashSet<String>>) iter.next();
62
            System.out.println(entry.getKey()+" "+entry.getValue().toString());
63
        }
64
    }
65

66
    private static void kshell_func(){
67
        int k=1;
68
        kmap.clear();
69

70
        while (!map.isEmpty()){
71
            HashSet<String> ktemp=new HashSet<String>();
72
            for (Iterator<Map.Entry<String,HashSet<String>>> iter = map.entrySet().iterator(); iter.hasNext();){
73
                Map.Entry<String,HashSet<String>> item = iter.next();
74
                if (item.getValue().size()<=k){
75
                    ktemp.add(item.getKey())
76
                    for (String i:item.getValue()){
77
                        HashSet<String> temp=map.get(i);
78
                        temp.remove(item.getKey());
79
                    }
80
                    iter.remove();
81
                }
82
            }
83

84
            // Iterator iter=map.entrySet().iterator();
85
            // Map.Entry<String,HashSet<String>> entry=(Map.Entry<String,HashSet<String>>) iter.next();
86
            // while (iter.hasNext()){
87
            //     if (entry.getValue().size()<=k){
88
            //         ktemp.add(entry.getKey());
89
            //         for (String index:entry.getValue()){
90
            //             HashSet<String> temp=map.get(index);
91
            //             temp.remove(entry.getKey());
92
            //         }
93
            //         String keytemp=entry.getKey();
94
            //         entry=(Map.Entry<String,HashSet<String>>) iter.next();
95
            //         map.remove(keytemp);
96
            //         System.out.println("delete ...");
97
            //     }
98
            // }
99
            kmap.put(Integer.valueOf(k),ktemp);
100
            k=k+1;
101
        }
102
    }
103

104
    private static void printkmap(){
105
        Iterator iter=kmap.entrySet().iterator();
106
        while(iter.hasNext()){
107
            Map.Entry<Integer,HashSet<String>> entry=(Map.Entry<Integer,HashSet<String>>) iter.next();
108
            System.out.println(entry.getKey().toString()+" "+entry.getValue().toString());
109
        }
110
    }
111
    public static void main(String[] args) {
112
        loadfile("./data.txt");
113
        //mapprint();
114
        kshell_func();
115
        //mapprint();
116
        printkmap();
117
        System.out.println("complete");
118

119
    }
120
}