Java共现矩阵的构建(用于社交网络结构分析)

秒速五厘米 2023-08-17 15:46 128阅读 0赞

本文作者：**合肥工业大学 电子商务研究所 钱洋** email：1563178220@qq.com 。  
**内容可能有不到之处，欢迎交流。  
未经本人允许禁止转载。**

### 文章目录 ###

*  背景
 *  Java实现共现矩阵
 *  程序运行结果
 *  关于社区发现算法

# 背景 #

最近，在做研究的时候，需要使用到Louvain社区检测算法(Louvain Community Detection)。而该算法的输出是节点-节点或节点-节点-权重。如节点-节点的格式如下：

0 1
    0 2
    0 3
    0 4
    1 3
    2 5
    3 5
    4 6
    ...

而对于一些网络数据，节点与节点之间是存在权重的（表明节点之间的连接强弱）。例如，文献合作网络：  
![在这里插入图片描述][20190927112329818.png_pic_center]  
在比如，点击流网络：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center]  
上面的点击流网络，可以转化成如下形式的共现矩阵：  
![在这里插入图片描述][20190927112455819.png_pic_center]  
即可表示A-B的权重为4，A-C的权重为2等。

而本博客的目的，是将如下数据转化成节点-节点-权重的形式：

470 657 66
    2139 3204 3677 470 657
    109 111 2778 2980 3397 3405 3876 448
    117 4147
    375 66 470 657
    4083 66
    2541 3059
    2988 3104 375
    2088 2123 2304 2615 2778 3080 3195
    2123 2556
    16 453 50 813
    117 164 2561 3589 588 66
    659 771 3204 3677

转化后的数据形式如下：

470 66 2
    66 3589 1
    117 3589 1
    657 3204 1
    375 3104 1
    2123 2556 1
    2304 3195 1
    ...

下面，介绍如何使用Java实现这一过程。

# Java实现共现矩阵 #

下图为工程的目录结构：  
![在这里插入图片描述][20190927145631299.png_pic_center]

首先，介绍一下文件操作类FileUtils。其中，**readLines()负责读取数据，将writeLines()方法负责将ArrayList类型的数据写入指定文档，writeHashMap()方法负责将Hashtable类型的数据写入指定文档。**  
该类用于读取文本文件，将ArrayList

package cooccurrence;
    
    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    import java.util.ArrayList;
    import java.util.Hashtable;
    import java.util.Map;
    
    public class FileUtils { 
    	/** * 读文件 * @param file 输入文件 * @param lines 多行文本转化成集合 * @param code 输出文件编码 */
    	public static void readLines(String file, ArrayList<String> lines, String code) { 
    		BufferedReader reader = null;
    		try { 
    			reader = new BufferedReader( new InputStreamReader( new FileInputStream( new File(file)),code));
    			String line = null;
    			while ((line = reader.readLine()) != null) { 
    				lines.add(line);
    			}
    		} catch (FileNotFoundException e) { 
    			e.printStackTrace();
    		} catch (IOException e) { 
    			e.printStackTrace();
    		} finally { 
    			if (reader != null) { 
    				try { 
    					reader.close();
    				} catch (IOException e) { 
    					e.printStackTrace();
    				}
    			}
    		}
    
    	}
    	/** * 写文件 * @param file 输入文件 * @param lines 集合内容 * @param code 输出文件编码 */
    	public static void writeLines(String file, ArrayList<?> lines, String code) { 
    		BufferedWriter writer = null;
    		try { 
    			writer = new BufferedWriter( new OutputStreamWriter( new FileOutputStream( new File(file)),code));
    			for (int i = 0; i < lines.size(); i++) { 
    				writer.write(lines.get(i) + "\n");
    			}
    
    		} catch (FileNotFoundException e) { 
    			e.printStackTrace();
    		} catch (IOException e) { 
    			e.printStackTrace();
    		} finally { 
    			if (writer != null) { 
    				try { 
    					writer.close();
    				} catch (IOException e) { 
    					e.printStackTrace();
    				}
    			}
    		}
    	}
    	/** * 写文件 * @param file 输入文件 * @param hashmap HashMap集合 * @param code 输出文件编码 */
    	public static void writeHashMap(String file, Hashtable<?, ?> hashmap, String code) { 
    		BufferedWriter writer = null;
    		try { 
    			writer = new BufferedWriter( new OutputStreamWriter( new FileOutputStream( new File(file)),code));
    			for (Map.Entry<?, ?> entry : hashmap.entrySet()) { 
    				writer.write(entry.getKey() + " " + entry.getValue() + "\n");
    			}
    		} catch (FileNotFoundException e) { 
    			e.printStackTrace();
    		} catch (IOException e) { 
    			e.printStackTrace();
    		} finally { 
    			if (writer != null) { 
    				try { 
    					writer.close();
    				} catch (IOException e) { 
    					e.printStackTrace();
    				}
    			}
    		}
    	}
    }

下面，介绍核心的算法Pair：

package cooccurrence;
    
    
    public class Pair { 
    	public int w1;
    	public int w2;
    	public Pair(int w1,int w2){ 
    		this.w1 = min(w1, w2);
    		this.w2 = max(w1, w2);
    	}
    	private static int min(int x,int y){ 
    		if(x<y)
    			return x;
    		else
    			return y;
    	}
    	private static int max(int x,int y){ 
    		if(x>y)
    			return x;
    		else
    			return y;
    	}
    }

该类中的构造方法Pair()输入的是两个编过号的词，经过方法处理之后，将w1赋值为较小数字编号的词，将w2赋值为较大编号的词。举个例子：

输入：w1=1，w2=2
    或输入：w1=2，w2=1
    
    其输出结果都是：w1=1，w2=2

通过这种操作就会保证，生成的词对都是“小-大”的形式。

下面介绍CooccurrenceMatrix类。

package cooccurrence;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Hashtable;
    import java.util.List;
    import java.util.Map;
    
    public class CooccurrenceMatrix { 
    	//word to index
    	public Map<String, Integer> wordToIndexMap = new HashMap<String, Integer>();
    	//index to String word 
    	public List<String> indexToWordMap = new ArrayList<String>();  
    	public  int [][] docword;//word index array
    	public  int M; // 文档总数
    	public ArrayList<String> wordpair=new ArrayList<>();
    	public String code;  //输入输出文件编码
    	public String outputFileP; //输出共现词对
    	public String outputFilePMatr; //输出共现矩阵
    	/** * 创建一个构造方法 * @param inputFile 输入文件 * @param inputFileCode 输入文件和输入文件的编码 * @param outputFilePair 词对输出文件 * @param outputFile 词对频率输出文件 */
    	public CooccurrenceMatrix(String inputFile, String inputFileCode, String outputFilePair, String outputFileMatirx){ 
    		//读数据
    		ArrayList<String> docLines = new ArrayList<String>();
    		FileUtils.readLines(inputFile, docLines,inputFileCode);
    		M = docLines.size();
    		docword = new int[M][];  //重新编号文档
    		int j = 0;
    		//编号
    		for(String line : docLines){ 
    			//基于空格分割文件
    			String[] words = line.split(" ");
    			docword[j] = new int[words.length];
    			for(int i = 0; i < words.length; i++){ 
    				String word = words[i];
    				if(!wordToIndexMap.containsKey(word)){ 
    					int newIndex = wordToIndexMap.size();
    					wordToIndexMap.put(word, newIndex);
    					indexToWordMap.add(word);
    					docword[j][i] = newIndex;
    				} else { 
    					docword[j][i] = wordToIndexMap.get(word);
    				}
    			}
    			j++;
    		}
    		code = inputFileCode;
    		outputFileP = outputFilePair;
    		outputFilePMatr = outputFileMatirx;
    	}
    	//共现处理
    	public void toMatrix(){ 
    		System.out.println("......开始产生共现词对.........");
    		//循环每篇文档，产生共现词对
    		for(int docu = 0;docu < M; docu++){ 
    			//对文档的词进行循环
    			for(int i = 0; i < docword[docu].length; i++)
    				for(int j = i+1;j < docword[docu].length; j++){ 
    					//空格分割
    					String wordp = indexToWordMap.get(new Pair(docword[docu][i],docword[docu][j]).w1) + " " + indexToWordMap.get(new Pair(docword[docu][i],docword[docu][j]).w2);
    					wordpair.add(wordp);
    					FileUtils.writeLines(outputFileP, wordpair, code);
    				}
    		}
    		System.out.println("......写入共现词对,统计词对频率.........");
    		//统计词对的频率
    		Hashtable<String, Integer>  wordCount = new Hashtable<String, Integer>();
    		for (int pair = 0; pair < wordpair.size(); pair++) { 
    			if (!wordCount.containsKey(wordpair.get(pair))) { 
    				wordCount.put(wordpair.get(pair), Integer.valueOf(1));
    			} else { 
    				wordCount.put(wordpair.get(pair), Integer.valueOf(wordCount.get(wordpair.get(pair)).intValue() + 1));
    			}
    		}
    		//写入文档
    		FileUtils.writeHashMap(outputFilePMatr, wordCount, code);
    		System.out.println("......写入词对频率结束.........");
    	}
    	
    	public static void main(String[] args) { 
    		CooccurrenceMatrix matrix = new CooccurrenceMatrix("cooccurrencedata/train_raw.txt", "gbk", "cooccurrencedata/cpair.txt", "cooccurrencedata/cmatrix.txt");
    		matrix.toMatrix();
    	}
    
    }

该类的构造方法CooccurrenceMatrix()的输入参数包括：

/**
    	 * 创建一个构造方法
    	 * @param inputFile 输入文件
    	 * @param inputFileCode 输入文件和输入文件的编码
    	 * @param outputFilePair  词对输出文件
    	 * @param outputFile  词对频率输出文件
    	 */

其中，docword数组存储文档数据(重新编号后的)。toMatrix()方法，首先利用Pair类产生共现词对，之后利用FileUtils中的writeLines()方法将其写入指定文件；接着，我对所有产生的词对统计频率（这里使用了Hashtable集合），最后，利用FileUtils类中的writeHashMap()方法将其写入指定文件。

# 程序运行结果 #

运行CooccurrenceMatrix类，可以看到工程目录下的cooccurrencedata文件夹多了两个文件，即共现词对文件和词对频率文件。“cpair.txt”文件内容如下：

470 657
    470 66
    657 66
    2139 3204
    2139 3677
    470 2139
    657 2139
    3204 3677
    470 3204
    657 3204
    470 3677
    ...

“cmatrix.txt”文件内容如下：

470 66 2
    66 3589 1
    117 3589 1
    657 3204 1
    375 3104 1
    2123 2556 1
    2304 3195 1
    66 588 1
    2088 3080 1
    3589 588 1
    3080 3195 1
    50 813 1
    ...

# 关于社区发现算法 #

Louvain算法对应的论文为：  
Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks\[J\]. Journal of statistical mechanics: theory and experiment, 2008, 2008(10): P10008.  
![在这里插入图片描述][20190927153645361.png_pic_center]  
从引用次数可以看出其影响力。  
该算法可使用Gephi进行可视化，读者可参考下面这篇博客进行操作：

https://blog.csdn.net/eastmount/article/details/85046305

如下为笔者使用Gephi所做的一个图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 1]

[20190927112329818.png_pic_center]: /images/20230810/519f7ded71824351ab2b5120634ea1f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230810/531828825dc0456a96a38b33b4f4974d.png
[20190927112455819.png_pic_center]: /images/20230810/d8f7caa0829041199aa71e6d0b1cca43.png
[20190927145631299.png_pic_center]: /images/20230810/7ee0d18b1efa42a69528d68f09005d79.png
[20190927153645361.png_pic_center]: /images/20230810/8dd2e185681e4fa99793ca66abdbc965.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230810/277258eae89b44b58d730d2f6474eb83.png