基于SNA的网络核心及社团结构挖掘研究
|
摘要
社会网络指的是社会行动者及其间的关系集合。也可以说一个社会网络是由多个点(社会行动者)和各点之间的连线(行动者之间的联系)组成的集合。因此社会网络分析不同于单个的语义分析,是注重于关系数据的分析。
本文主要围绕应用于网络信息安全的社会网络分析法这一方向展开,研究了基于邮件的社会网络分析,在广泛阅读了国内外文献的基础之上提出了一种基于邮件挖掘社会网络核心层的新方法,本文的主要工作主要有以下两个方面:
(1)为了挖掘出完整的社会网络核心层的成员,提出了基于邮件挖掘社会网络核心层的新方法。在用邮件数据构建出了社会网络之后,首先删除节点度小于一定阈值的节点,再运用社团结构挖掘及中心度分析找出部分网络核心成员,最后结合已删除的节点得出完整的网络核心层。实验结果显示,该方法可以找出全部的网络核心成员,且在一定程度上解决了大型网络不容易计算的问题。
(2)为了更精确的评价社团结构,本文提出了一种新的评价标准——社团凝聚度,定义社团外部链接数与内部连接数的比值为社团凝聚度,并在此基础上提出了基于局部社团凝聚度增量的社团结构挖掘算法。首先选择初始节点定义为一个社团,然后比较网络中每个节点加入到社团后的凝聚度增量,选择局部社团凝聚度增量增长最快或者减少最慢的节点作为社团成员加入,重复选择合适节点加入社团直到社团凝聚度达到指定阈值,或者发现完全封闭的社团。最后比较挖掘出社团的凝聚度可以确定哪些为社团,哪些则可以作为孤立点。
针对本文提出的算法编写程序,应用于计算机生成网络和一个虚拟企业网络,实验结果表明算法是高效的和实用的。
Social network refers to the actors and the social relationship between actors. That is to say that a social network is a set composed of a number of points (social actors) and the connection between points (the link between actors). Therefore, social network analysis is different from a single semantic analysis is to focus on the relational data analysis.
This article applies to network information security around the social network analysis started in this direction. This paper studies the social network analysis based on e-mail. In this paper, extensive reading at home and abroad based on the literature presents a social network based on excavation e-mail new method for the core layer. The innovation of this paper mainly in the following two aspects:
(1)In order to tap the core of complete social network layer members, this paper, mining social networks based on e-mail new method for the core layer. Using e-mail the data to build out a social network, the first delete the node is less than a certain threshold value of the node, then the use of Community Structure Mining and Analysis Center, part of the network to identify the core members of the deleted node last, come to a complete network of core layer. Experimental results show that this method can identify all of the core members of the network, but also to some extent is not easy to solve large-scale network computing problems.
(2)In order to more precisely evaluate the degree of polymerization associations proposed in this paper based on the degree of community cohesion of the community structure of incremental mining algorithm. The definition of community External Web Link Counts and internal connections for the community cohesion ratio of the number of degrees, first select the initial node is defined as a society, and then compare the network each node added to the degree of community cohesion after the increment, select local community cohesion degree increments up to the fastest or the slowest node to reduce community members as a repeat selection to find the smallest node join the community until the specified number of members of the community, or find completely closed societies. Comparing the final excavated to determine what degree of community cohesion as a society, and which can be as isolated points.
This paper presents an algorithm for programming applied to computer generated networks and a virtual enterprise network, experimental results show that the algorithm is efficient and practical.
本文主要围绕应用于网络信息安全的社会网络分析法这一方向展开,研究了基于邮件的社会网络分析,在广泛阅读了国内外文献的基础之上提出了一种基于邮件挖掘社会网络核心层的新方法,本文的主要工作主要有以下两个方面:
(1)为了挖掘出完整的社会网络核心层的成员,提出了基于邮件挖掘社会网络核心层的新方法。在用邮件数据构建出了社会网络之后,首先删除节点度小于一定阈值的节点,再运用社团结构挖掘及中心度分析找出部分网络核心成员,最后结合已删除的节点得出完整的网络核心层。实验结果显示,该方法可以找出全部的网络核心成员,且在一定程度上解决了大型网络不容易计算的问题。
(2)为了更精确的评价社团结构,本文提出了一种新的评价标准——社团凝聚度,定义社团外部链接数与内部连接数的比值为社团凝聚度,并在此基础上提出了基于局部社团凝聚度增量的社团结构挖掘算法。首先选择初始节点定义为一个社团,然后比较网络中每个节点加入到社团后的凝聚度增量,选择局部社团凝聚度增量增长最快或者减少最慢的节点作为社团成员加入,重复选择合适节点加入社团直到社团凝聚度达到指定阈值,或者发现完全封闭的社团。最后比较挖掘出社团的凝聚度可以确定哪些为社团,哪些则可以作为孤立点。
针对本文提出的算法编写程序,应用于计算机生成网络和一个虚拟企业网络,实验结果表明算法是高效的和实用的。
Social network refers to the actors and the social relationship between actors. That is to say that a social network is a set composed of a number of points (social actors) and the connection between points (the link between actors). Therefore, social network analysis is different from a single semantic analysis is to focus on the relational data analysis.
This article applies to network information security around the social network analysis started in this direction. This paper studies the social network analysis based on e-mail. In this paper, extensive reading at home and abroad based on the literature presents a social network based on excavation e-mail new method for the core layer. The innovation of this paper mainly in the following two aspects:
(1)In order to tap the core of complete social network layer members, this paper, mining social networks based on e-mail new method for the core layer. Using e-mail the data to build out a social network, the first delete the node is less than a certain threshold value of the node, then the use of Community Structure Mining and Analysis Center, part of the network to identify the core members of the deleted node last, come to a complete network of core layer. Experimental results show that this method can identify all of the core members of the network, but also to some extent is not easy to solve large-scale network computing problems.
(2)In order to more precisely evaluate the degree of polymerization associations proposed in this paper based on the degree of community cohesion of the community structure of incremental mining algorithm. The definition of community External Web Link Counts and internal connections for the community cohesion ratio of the number of degrees, first select the initial node is defined as a society, and then compare the network each node added to the degree of community cohesion after the increment, select local community cohesion degree increments up to the fastest or the slowest node to reduce community members as a repeat selection to find the smallest node join the community until the specified number of members of the community, or find completely closed societies. Comparing the final excavated to determine what degree of community cohesion as a society, and which can be as isolated points.
This paper presents an algorithm for programming applied to computer generated networks and a virtual enterprise network, experimental results show that the algorithm is efficient and practical.
引文
[1] Kar van Meter.Terrorists/Liberators:Researching and Dealing with adversary social networks.Paris:LASMAS-CNRS,1998
[2] Petros Drineas,Mukkai S.Krishnamoorthy,Michael D.Sofka,Bulent Yener.Studying E-mail Graphs for Intelligence Monitoring and Analysis in the Absence of Semantic Information[J].Intelligence and Security Informatics,2003,13(6) :53-79
[3]国家社会科学基金项目2004年度课题指南.2003-12-16
[4]李鹏翔,任玉晴.网络节点(集)重要性的一种度量指标.系统科学,2004,20(4) :13-20
[5]王霄宁.基于社会网络分析的产业集群定量化模型.统计与决策,2005,3:43-45
[6]王霄宁.基于社会网络分析的产业集群建模及实证检验.系统工程,2005,23(3) :115-119
[7]张其仔.新经济社会学.中国社会科学出版社,北京.2001,1
[8]姚小涛,席酉民.社会网络理论及其在企业研究中的应用.西安交通大学学报(社会科学版),2003(3):22-27 [9 ] Peter Andrews.Executive Tek Report:Social Network Analysis- Tracing relationships.IBM Global Services,2002
[10] Rob Cross,Andrew Parker,Steve Borgatti.用社会网络分析知识改进的创新与共享.http://ibm.com/services/strategy
[11] Analytic Technologies.Ucinet 6 for Windows:Software for Social Networks Analysis.Harvard
[12] Batagelj V,Mrvar A.Pajek - Analysis and Visualization of Large Networks.LNCS 2265,Springer-Verlag,2001,477-478
[13] Wasserman S,K Faust.Social Network Analysis:Methods and Applications.Cambridge University Press,1994
[14] Arabie,P,S.A.Boorman,and P.R.Lebitt.Constructing block models:How and why,Journal of Mathematical Psychology,1978,17:21 - 63
[15] Baker,Wayne E.Three - dimensional block models.Journal of Mathematical Sociology,1986,12:191 - 223
[16] Burt,Ronald and M.J.Minor.Structural Holes:The Social Structure of Competition,Harvard University Press,1992,3:23-26
[17]肖冬平,梁臣.社会网络研究的理论模式综述.广西社会科学,2003,12:166-168
[18] Doreian,Patrick.On the connectivity of social networks.Journal of Mathematical Sociology,1974,3:245 - 258
[19] Mustafa Emirbayer,Jeff Goodwin.Network Analysis,Culture,and the Problem of Agency.American Journal of Sociology,1999,6:1411 - 1454
[20]刘军.社会网络模型研究论析.社会学研究,2004,1:1-12
[21]李林艳.社会空间的另一种想象--社会网络分析的结构视野.社会学研究,2004,3:64-75
[22]刘军.社会网络分析导论.北京:社会科学文献出版社,2004
[23]罗家德.社会网分析讲义.北京:社会科学文献出版社,2005
[24] Scott J.Social Network Analysis:A Handbook.2nd ed. London:Sage Publications,2002
[25] Girvan M,Newman M E J.Community structure in social and biological networks.Proc.Natl. Acad.Sci,2002,99(12) :7821-7826
[26] Newman M E J,Girvan M.Finding and evaluating community structure in networks.Phys.Rev.E, 2004,69(2):026113-026127
[27] Zachary W.An information flow model for conflict and fission in small groups.Journal of Anthropological Research,1977,33(4) :452-473
[28] Castellano C,Cecconi F,Loreto V,et a Self-contained algorithms to detect communities in networks.Eur.Phys.J.B,2004,38:311-319
[29] Donetti L,Munoz M.Detecting network communities:a new systematic and efficient algorithm. Stat. Mech.,2004,10:P10012
[30] Castellano C,Cecconi F,Loreto V,et al.Self-contained algorithms to detect communities in networks.Eur. Phys. J. B,2004,38:311-319
[31] Fortunato S,Latora V,Marchiori M.Method to find community structures based on information centrality.Phys.Rev.E,2004,70(5) :056104-056116
[32] NewmanM E J. Fast algorithm for detecting community structure in networks.Phys Rev E,2004, 69 (6) :066133
[33]赵鹏,蔡庆生,王清毅.交联网络中的可重叠社团结构分析算法.华南理工大学学报,2008,36(5) :19-23
[34]朱大勇,侯晓荣,张新丽.遗传聚类的社团结构发现.智能系统学报,2009,2,4(1) :81-84
[35]王立敏,高学东,宫雨,马红权.基于相对密度的社团结构探测算法.计算机工程,2009,1,1:117-119
[36]段丹,郭绍忠,李志博,刘沙.基于邮件分类的敏感社团挖掘技术.计算机应用,2007,12,27(12) :3039-3041
[37]高鹏,曹先彬.基于社会网络的聊天数据噪声过滤.计算机工程,2008,3,34(5) :166-168
[38]尹洪章,曹先彬.结合内容相似性和时序性的社会网络挖掘.计算机工程,2008,3,34(1) :83-85
[39]郭绍忠,段丹,刘晓楠,甄涛.邮件挖掘技术在社会网络分析中的研究与应用,计算机工程与设计,2008,5,29(9) :2339-2341
[40]唐策善,李龙澍,黄刘生.数据结构——用C语言描述.北京:高等教育出版社,2004:143-147
[41]乔少杰,唐常杰.基于个性特征仿真邮件分析系统挖掘犯罪网络核心,计算机学报,2008,10,31(10) :1795-1803
[42] Scott J.Social Network Analysis:A Handbook.2nd ed.London:Sage Publications,2000
[43] Wasserman S,Faust K,Social Network Analysis.Cambridge University Press,Cambridge,1994
[44] Moody J.Race school integration and friendship segregation in America.Am.J.Sociol.,2001, 107(3):679-716
[45]王立敏,高学东.基于最小社团链接度增量的社团结构挖掘算法,北京科技大学学报,2009,1,31(1) :112-117
[2] Petros Drineas,Mukkai S.Krishnamoorthy,Michael D.Sofka,Bulent Yener.Studying E-mail Graphs for Intelligence Monitoring and Analysis in the Absence of Semantic Information[J].Intelligence and Security Informatics,2003,13(6) :53-79
[3]国家社会科学基金项目2004年度课题指南.2003-12-16
[4]李鹏翔,任玉晴.网络节点(集)重要性的一种度量指标.系统科学,2004,20(4) :13-20
[5]王霄宁.基于社会网络分析的产业集群定量化模型.统计与决策,2005,3:43-45
[6]王霄宁.基于社会网络分析的产业集群建模及实证检验.系统工程,2005,23(3) :115-119
[7]张其仔.新经济社会学.中国社会科学出版社,北京.2001,1
[8]姚小涛,席酉民.社会网络理论及其在企业研究中的应用.西安交通大学学报(社会科学版),2003(3):22-27 [9 ] Peter Andrews.Executive Tek Report:Social Network Analysis- Tracing relationships.IBM Global Services,2002
[10] Rob Cross,Andrew Parker,Steve Borgatti.用社会网络分析知识改进的创新与共享.http://ibm.com/services/strategy
[11] Analytic Technologies.Ucinet 6 for Windows:Software for Social Networks Analysis.Harvard
[12] Batagelj V,Mrvar A.Pajek - Analysis and Visualization of Large Networks.LNCS 2265,Springer-Verlag,2001,477-478
[13] Wasserman S,K Faust.Social Network Analysis:Methods and Applications.Cambridge University Press,1994
[14] Arabie,P,S.A.Boorman,and P.R.Lebitt.Constructing block models:How and why,Journal of Mathematical Psychology,1978,17:21 - 63
[15] Baker,Wayne E.Three - dimensional block models.Journal of Mathematical Sociology,1986,12:191 - 223
[16] Burt,Ronald and M.J.Minor.Structural Holes:The Social Structure of Competition,Harvard University Press,1992,3:23-26
[17]肖冬平,梁臣.社会网络研究的理论模式综述.广西社会科学,2003,12:166-168
[18] Doreian,Patrick.On the connectivity of social networks.Journal of Mathematical Sociology,1974,3:245 - 258
[19] Mustafa Emirbayer,Jeff Goodwin.Network Analysis,Culture,and the Problem of Agency.American Journal of Sociology,1999,6:1411 - 1454
[20]刘军.社会网络模型研究论析.社会学研究,2004,1:1-12
[21]李林艳.社会空间的另一种想象--社会网络分析的结构视野.社会学研究,2004,3:64-75
[22]刘军.社会网络分析导论.北京:社会科学文献出版社,2004
[23]罗家德.社会网分析讲义.北京:社会科学文献出版社,2005
[24] Scott J.Social Network Analysis:A Handbook.2nd ed. London:Sage Publications,2002
[25] Girvan M,Newman M E J.Community structure in social and biological networks.Proc.Natl. Acad.Sci,2002,99(12) :7821-7826
[26] Newman M E J,Girvan M.Finding and evaluating community structure in networks.Phys.Rev.E, 2004,69(2):026113-026127
[27] Zachary W.An information flow model for conflict and fission in small groups.Journal of Anthropological Research,1977,33(4) :452-473
[28] Castellano C,Cecconi F,Loreto V,et a Self-contained algorithms to detect communities in networks.Eur.Phys.J.B,2004,38:311-319
[29] Donetti L,Munoz M.Detecting network communities:a new systematic and efficient algorithm. Stat. Mech.,2004,10:P10012
[30] Castellano C,Cecconi F,Loreto V,et al.Self-contained algorithms to detect communities in networks.Eur. Phys. J. B,2004,38:311-319
[31] Fortunato S,Latora V,Marchiori M.Method to find community structures based on information centrality.Phys.Rev.E,2004,70(5) :056104-056116
[32] NewmanM E J. Fast algorithm for detecting community structure in networks.Phys Rev E,2004, 69 (6) :066133
[33]赵鹏,蔡庆生,王清毅.交联网络中的可重叠社团结构分析算法.华南理工大学学报,2008,36(5) :19-23
[34]朱大勇,侯晓荣,张新丽.遗传聚类的社团结构发现.智能系统学报,2009,2,4(1) :81-84
[35]王立敏,高学东,宫雨,马红权.基于相对密度的社团结构探测算法.计算机工程,2009,1,1:117-119
[36]段丹,郭绍忠,李志博,刘沙.基于邮件分类的敏感社团挖掘技术.计算机应用,2007,12,27(12) :3039-3041
[37]高鹏,曹先彬.基于社会网络的聊天数据噪声过滤.计算机工程,2008,3,34(5) :166-168
[38]尹洪章,曹先彬.结合内容相似性和时序性的社会网络挖掘.计算机工程,2008,3,34(1) :83-85
[39]郭绍忠,段丹,刘晓楠,甄涛.邮件挖掘技术在社会网络分析中的研究与应用,计算机工程与设计,2008,5,29(9) :2339-2341
[40]唐策善,李龙澍,黄刘生.数据结构——用C语言描述.北京:高等教育出版社,2004:143-147
[41]乔少杰,唐常杰.基于个性特征仿真邮件分析系统挖掘犯罪网络核心,计算机学报,2008,10,31(10) :1795-1803
[42] Scott J.Social Network Analysis:A Handbook.2nd ed.London:Sage Publications,2000
[43] Wasserman S,Faust K,Social Network Analysis.Cambridge University Press,Cambridge,1994
[44] Moody J.Race school integration and friendship segregation in America.Am.J.Sociol.,2001, 107(3):679-716
[45]王立敏,高学东.基于最小社团链接度增量的社团结构挖掘算法,北京科技大学学报,2009,1,31(1) :112-117