QQ客服 官方微博 反馈留言

题名	网络社区结构的刻画与查找: 局部视角
作者	彭攀
学位类别	博士
答辩日期	2013-05-29
授予单位	中国科学院大学
授予地点	北京
导师	李昂生 ; 蔡进一
关键词	复杂网络 小社区现象 传导率 亚线性算法 局部探测算法 图性质检测
其他题名	Characterizing and Detecting the Community Structure in Networks: A Local Perspective
学位专业	计算机软件与理论
中文摘要	我们从局部的视角研究网络中社区结构的刻画与查找问题。网络中的社区是一组内部联系紧密、与外部联系较稀疏的一组点集。社区可以看作是网络的基本单元或构建模块，并且它在社会感染、蛋白质功能预测、市场营销、垃圾邮件检测、信息查找等诸多领域有重要应用。 我们从随机图的角度来模拟网络中的社区结构，随机图的优势是可以用局部的（概率的）生成规则来描述大型的复杂网络。我们给出了一个新的社区定义，并基此提出了网络中的小社区现象：即网络中几乎每个点都属于某个小的社区。该现象反映的一个直观是社会上几乎每个人都属于某个小的团体，即家庭、朋友、同事等等。我们考虑经典网络模型上小社区现象的存在性问题，并给出正面的和负面的结果：有的模型上的确存在小社区现象，而有的却不存在。我们还提出了两个同时具有小社区现象，小直径性质和度的幂律分布现象的几何偏好依附网络模型。 我们设计并分析了几个查找和检测社区结构的局部算法。这些局部算法都只需要读取网络中的部分信息，并可以输出质量有理论保证的结果。具体地说，我们给出了两个查找稠密二部状子图的局部探测算法，并给出了一个检测图中是否存在小的稠密二部状子图的局部性质检测算法，这里集合稠密二部状的性质由稠密二部值来度量。研究稠密二部状子图的意义在于它刻画了WWW网络中的社区结构。我们还给出了一个检测网络中是否存在小的稠密子图的局部性质检测算法，这里集合的稠密性由其传导率来度量。
英文摘要	We investigate the problem of modeling and (algorithmically)  identifying the community structure of a network from a local  perspective. A community in a network is usually referred to a subset of nodes with dense intra-connections and (relatively) sparse inter-connections. Communities can be seen as building blocks or basic elements of networks and have found applications in social contagion, protein function prediction, marketing, spam detection, searching and many other areas. For the modeling part, we study the property of community structure by using random graphs, which allow us to use local (and probabilistic) rules to describe large-scale networks. We give a new definition of community, based on which we propose a new concept called the small community phenomenon, that is, almost every node in the network belongs to some small community, which formally characterize the common experience that almost every one in our society belongs to some small densely connected groups, such as families, friends, colleagues et al. We study the problem of whether existing classic network models exhibit the small community phenomenon or not and establish both positive and negative results: the small community phenomenon do exist in some models, while it does not exist in some other models. We also give geometric network models that simultaneously have the small diameter property, the power law degree distribution as well as the small community phenomenon. For the algorithmic part, we design and analyze several local algorithms, which only need to explore a small portion of the input graph and give output with theoretical guarantees on the quality, for finding and testing the community structure. Our local algorithms include two local exploration algorithms to extract dense bipartite-like subgraphs which characterize cyber-communities in WWW graphs, a property testing algorithm to test if a network contains no small dense bipartite-like subgraph, where we use the bipartiteness score as the measure of dense bipartiteness, and a property testing algorithm to test if a network contains no small dense subgraph, where we use the expansion as the measure of density.
语种	中文
学科主题	计算机科学技术基础学科 ; 算法理论 ; 数据结构 ; 计算机科学技术基础学科其他学科 ; 人工智能 ; 人工智能理论 ; 模式识别 ; 人工智能其他学科
公开日期	2013-05-31
内容类型	学位论文
源URL	[http://ir.iscas.ac.cn/handle/311060/14832]
专题	软件研究所_计算机科学国家重点实验室 _学位论文
推荐引用方式 GB/T 7714	彭攀. 网络社区结构的刻画与查找: 局部视角[D]. 北京. 中国科学院大学. 2013.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。