中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
Subject: 计算机科学技术基础学科 ; 计算机科学技术基础学科::算法理论 ; 计算机科学技术基础学科::数据结构 ; 计算机科学技术基础学科::计算机科学技术基础学科其他学科 ; 人工智能 ; 人工智能::人工智能理论 ; 人工智能::模式识别 ; 人工智能::人工智能其他学科
Title:
网络社区结构的刻画与查找: 局部视角
Author: 彭攀
Issued Date: 2013-05-29
Supervisor: 李昂生 ; 蔡进一
Major: 计算机软件与理论
Degree Grantor: 中国科学院大学
Place of Degree Grantor: 北京
Degree Level: 博士
Keyword: 复杂网络 ; 小社区现象 ; 传导率 ; 亚线性算法 ; 局部探测算法 ; 图性质检测
Alternative Title: Characterizing and Detecting the Community Structure in Networks: A Local Perspective
Abstract: 我们从局部的视角研究网络中社区结构的刻画与查找问题。网络中的社区是一组内部联系紧密、与外部联系较稀疏的一组点集。社区可以看作是网络的基本单元或构建模块,并且它在社会感染、蛋白质功能预测、市场营销、垃圾邮件检测、信息查找等诸多领域有重要应用。

我们从随机图的角度来模拟网络中的社区结构,随机图的优势是可以用局部的(概率的)生成规则来描述大型的复杂网络。我们给出了一个新的社区定义,并基此提出了网络中的小社区现象:即网络中几乎每个点都属于某个小的社区。该现象反映的一个直观是社会上几乎每个人都属于某个小的团体,即家庭、朋友、同事等等。我们考虑经典网络模型上小社区现象的存在性问题,并给出正面的和负面的结果:有的模型上的确存在小社区现象,而有的却不存在。我们还提出了两个同时具有小社区现象,小直径性质和度的幂律分布现象的几何偏好依附网络模型。

我们设计并分析了几个查找和检测社区结构的局部算法。这些局部算法都只需要读取网络中的部分信息,并可以输出质量有理论保证的结果。具体地说,我们给出了两个查找稠密二部状子图的局部探测算法,并给出了一个检测图中是否存在小的稠密二部状子图的局部性质检测算法,这里集合稠密二部状的性质由稠密二部值来度量。研究稠密二部状子图的意义在于它刻画了WWW网络中的社区结构。我们还给出了一个检测网络中是否存在小的稠密子图的局部性质检测算法,这里集合的稠密性由其传导率来度量。
English Abstract: 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.
Language: 中文
Content Type: 学位论文
URI: http://ir.iscas.ac.cn/handle/311060/14832
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
mythesis.pdf(1182KB)----限制开放 联系获取全文

Recommended Citation:
彭攀. 网络社区结构的刻画与查找: 局部视角[D]. 北京. 中国科学院大学. 2013-05-29.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[彭攀]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[彭攀]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace