博文
网络社团结构探测和矩阵分解模型
||
复杂网络中经常是有社团结构的。对社团结构目前还难于给出一个明确的数学化的定义，可以大体上将社团结构描述为网络中的一个顶点集，其内部连接是紧密的，而与外部的连接是疏松的。许多证据表明，社团结构经常是有其特殊含义的。比如说，在生物网络中，社团结构经常是一个功能模块或者通路，而在社会网中，社团结构经常是由一群持相同观点的人组成，在科研合作网中，社团结构则经常是某一个科研领域等等。比较经典的例子是空手道俱乐部人际关系网，里面有34名成员，分成两个社团结构([1])。文献中已经发展了大量有趣的模型来探测复杂社会网络中的社团结构。这些模型根据研究视角的不同大体可以分为两类：图分割模型和分层模型。 图分割模型将网络看做一个整体，经常是通过优化某些描述网络结构的目标函数来达到分割网络的目的, 比如优化模块化函数 Q([2])。 具体的模型包括文献[2]中的方法, 谱聚类模型 ([3,4])以及基于非负矩阵分解的模型([5,6])等.而分层模型则正好相反，正如其名字所表达的那样，其试图建立一个网络中顶点的分层结构或者是树状的聚类结构，该类模型一般有两种："从下至上"和"从上到下"。第一种类型的模型开始的时候，将每一个顶点看做一个独立的社团，然后逐步地将这些社团合并，而第二种类型的模型开始的时候，将所有的顶点放在一起，看做一个大的社团，然后将这个社团逐步地分割开。具体的模型包括文献[7,8]中的方法。
就我个人的看法，我比较喜欢非负矩阵分解类型的模型来处理社团结构探测问题，这个原因主要有两点，第一，网络社团结构探测问题本质上是属于无监督学习的范畴，而非负矩阵分解模型(Nonnegative Matrix Factorization, NMF，[9,10])在无监督学习领域获得了成功的应用，包括图像处理，基因表达，文本处理，多媒体数据分析等。总之,NMF具有自动探测数据背后隐藏模式方面的良好能力；第二，本人之前在矩阵分解方面做了一些工作，在感情上比较喜欢这个模型， :-）
事实上，已经有一些工作，使用NMF来探测网络社团结构了，包括[5,6]等,其中最近一个有趣的工作是对称非负矩阵分解模型. 尽管已经发展了各种不同的基于NMF的模型来探测网络社团结构，几乎所有这些模型都是通过 multiplicative update rules ([7,8])来求解的。这个算法收敛速度慢，比较费时，因此并不适合处理大规模问题. 我们提出使用字典学习算法 (DL) 来探测网络社团结构. DL 首先是为图像数据和生物数据而提出的 ([11])，并且已经被成功应用于数据聚类和分类问题 ([12])。我们提出了一种简化的字典学习算法，并将其应用于社团结构探测问题。在人工合成数据集和实际网络数据集上的实验结果表明：1) 标准字典学习算法和简化算法都比现有算法收敛的更快； 2) 并且, 相较于现有模型/算法，包括标准字典学习算法，我们提出的简化算法能得到更好的数值结果.
简言之,我们的工作有三个方面值得一提: 1. 当然是提出了新的模型来做社团结构探测; 2. 提出了新的人工数据生成准则. 当前做社团结构探测所用的人工数据都太过简单,规模不够大,结构单一,所以我们提出了新的生成办法,这是一个贡献; 3. 据我们所知,比较而言(包括Physica A上的同类文献)我们所使用的实际数据数量是最多的,包括7个网络数据和4个文本数据. 基于这些人工数据和实际数据,我们比同类文献的数值分析更彻底和全面.因而我们对我们的模型很有信心,呵呵呵呵.
欢迎各位博友的批评和建议.如果各位博友有兴趣,我还可以对各种矩阵分解模型做一个介绍.
文章网址: http://www.springerlink.com/content/p841234566513303/
http://info.scichina.com:8083/sciF/CN/volumn/current.shtml
【1】 Zachary W, An informative flow model for conflict and fission in small groups, J. Anthropos Res., 1977,33:452-473.
【2】 Newman M, Girvan M, Finding and evaluating community structure in networks, Phys. Rev. E., 2004,69: 026113
【3】 Pujol J, Bejar J, Delgado J, Clustering algorithm for determining community structure in large networks, Phys. Rev. E, 2006, 71:016107
【4】 White S, Smyth P, A spectral clustering approach to finding communities in graphs, In SDM, 2005:76-84
【5】 Wang F, Li T, Wang X, Community discovery using nonnegative matrix factorization, Dat. Min. Know. Dis., 2011,22:493-521
【6】 Ma X, Gao L, Yong X, Fu L, Semi-supervised clustering algorithm for community structure detection in complex netwroks, Physica A, 2010, 389: 187-197
【7】Newman M, Detecting community structure in networks, Eur.Phys.J, 2004,38: 321-330
【8】 Wasserman S,Faust K, Social network analysis: methods and applications, structrual analysis in the social sciences, Cambirdge,1994
【9】 Lee D, Seung H, Learning the parts of objects by nonnegative matrix factorization, Nature, 1999, 401:788-791
【10】Lee D, Seung H, Algorithms for nonnegative matrix factorization, NIPS, 2001: 556-562
【11】Mairal J, Bach F, Ponce J, Online learning for matrix factorization and sparse coding, J Mach. Learn. Res., 2010,11: 19-60
【12】Ramirez I, Sprechmann P, Sapiro G, Classification and clustering via dictionary learning with structured incoherence and shared features, CVPR, 2010: 3501-3508
https://wap.sciencenet.cn/blog-297051-503010.html
下一篇：非负矩阵分解模型的费用函数: 大繁至简
就我个人的看法，我比较喜欢非负矩阵分解类型的模型来处理社团结构探测问题，这个原因主要有两点，第一，网络社团结构探测问题本质上是属于无监督学习的范畴，而非负矩阵分解模型(Nonnegative Matrix Factorization, NMF，[9,10])在无监督学习领域获得了成功的应用，包括图像处理，基因表达，文本处理，多媒体数据分析等。总之,NMF具有自动探测数据背后隐藏模式方面的良好能力；第二，本人之前在矩阵分解方面做了一些工作，在感情上比较喜欢这个模型， :-）
事实上，已经有一些工作，使用NMF来探测网络社团结构了，包括[5,6]等,其中最近一个有趣的工作是对称非负矩阵分解模型. 尽管已经发展了各种不同的基于NMF的模型来探测网络社团结构，几乎所有这些模型都是通过 multiplicative update rules ([7,8])来求解的。这个算法收敛速度慢，比较费时，因此并不适合处理大规模问题. 我们提出使用字典学习算法 (DL) 来探测网络社团结构. DL 首先是为图像数据和生物数据而提出的 ([11])，并且已经被成功应用于数据聚类和分类问题 ([12])。我们提出了一种简化的字典学习算法，并将其应用于社团结构探测问题。在人工合成数据集和实际网络数据集上的实验结果表明：1) 标准字典学习算法和简化算法都比现有算法收敛的更快； 2) 并且, 相较于现有模型/算法，包括标准字典学习算法，我们提出的简化算法能得到更好的数值结果.
简言之,我们的工作有三个方面值得一提: 1. 当然是提出了新的模型来做社团结构探测; 2. 提出了新的人工数据生成准则. 当前做社团结构探测所用的人工数据都太过简单,规模不够大,结构单一,所以我们提出了新的生成办法,这是一个贡献; 3. 据我们所知,比较而言(包括Physica A上的同类文献)我们所使用的实际数据数量是最多的,包括7个网络数据和4个文本数据. 基于这些人工数据和实际数据,我们比同类文献的数值分析更彻底和全面.因而我们对我们的模型很有信心,呵呵呵呵.
欢迎各位博友的批评和建议.如果各位博友有兴趣,我还可以对各种矩阵分解模型做一个介绍.
文章网址: http://www.springerlink.com/content/p841234566513303/
http://info.scichina.com:8083/sciF/CN/volumn/current.shtml
【1】 Zachary W, An informative flow model for conflict and fission in small groups, J. Anthropos Res., 1977,33:452-473.
【2】 Newman M, Girvan M, Finding and evaluating community structure in networks, Phys. Rev. E., 2004,69: 026113
【3】 Pujol J, Bejar J, Delgado J, Clustering algorithm for determining community structure in large networks, Phys. Rev. E, 2006, 71:016107
【4】 White S, Smyth P, A spectral clustering approach to finding communities in graphs, In SDM, 2005:76-84
【5】 Wang F, Li T, Wang X, Community discovery using nonnegative matrix factorization, Dat. Min. Know. Dis., 2011,22:493-521
【6】 Ma X, Gao L, Yong X, Fu L, Semi-supervised clustering algorithm for community structure detection in complex netwroks, Physica A, 2010, 389: 187-197
【7】Newman M, Detecting community structure in networks, Eur.Phys.J, 2004,38: 321-330
【8】 Wasserman S,Faust K, Social network analysis: methods and applications, structrual analysis in the social sciences, Cambirdge,1994
【9】 Lee D, Seung H, Learning the parts of objects by nonnegative matrix factorization, Nature, 1999, 401:788-791
【10】Lee D, Seung H, Algorithms for nonnegative matrix factorization, NIPS, 2001: 556-562
【11】Mairal J, Bach F, Ponce J, Online learning for matrix factorization and sparse coding, J Mach. Learn. Res., 2010,11: 19-60
【12】Ramirez I, Sprechmann P, Sapiro G, Classification and clustering via dictionary learning with structured incoherence and shared features, CVPR, 2010: 3501-3508
https://wap.sciencenet.cn/blog-297051-503010.html
下一篇：非负矩阵分解模型的费用函数: 大繁至简
