Who Should Be Invited to My Party: A Size-Constrained k-Core Problem in Social Networks

来源 :计算机科学技术学报(英文版) | 被引量 : 0次 | 上传用户:weiyideta21
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
In this paper, we investigate the problem of a size-constrained k-core group query (SCCGQ) in social networks, taking both user closeness and network topology into consideration. More specifically, SCCGQ intends to find a group of h users that has the highest social closeness while being a k-core. SCCGQ can be widely applied to event planning, task assignment, social analysis, and many other fields. In contrast to existing work on the k-core detection problem, which aims to find a k-core in a social network, SCCGQ not only focuses on k-core detection but also takes size constraints into consideration. Although the conventional k-core detection problem can be solved in linear time, SCCGQ has a higher complexity. To solve the problem of SCCGQ, we propose a Blast Scatter (BS) algorithm, which appoints the query node as the center to begin outward expansions via breadth search. In each outward expansion, BS finds a new center through a greedy strategy and then selects multiple neighbors of the center. To speed up the BS algorithm, we propose an advanced search algorithm, called Bounded Extension (BE). Specifically, BE combines an effective social distance pruning strategy and a tight upper bound of social closeness to prune the search space considerably. In addition, we propose an offline social-aware index to accelerate the query processing. Finally, our experimental results demonstrate the efficiency and effectiveness of our proposed algorithms on large real-world social networks.
其他文献
期刊
2011年2月-6月我们启动了首届《中国人看世界》摄影大展,这一活动得到全国摄影爱好者的热烈响应,在短短的三个余月征稿期间内共收到有效作品近8400余幅,除中国大陆来稿以外,
期刊
1 引言Dr.A .Salomon(1 91 3)首次用普通X线机(钨靶)做乳腺X线摄影实验,摄取标本30 0 0例。Dr.StaffordWarren在1 930年首次应用于临床。Gros于1 96 9年首创钼靶X线机,70年
笔者于2003年在我县东关渔场进行了池塘主养云斑(鱼回)试验,取得了较好效果,现将试验报告如下.
为满足阿勒泰地区种植户的需要,提高种植户的种植水平,本文从栽培季节、育苗技术、定植方法、定植后田间管理、病虫草害防治等生产环节总结阿勒泰地区大棚秋冬茬芹菜高产栽培
乳腺癌是女性最常见的恶性肿瘤之一。早期诊断在乳腺癌的治疗中起着重要的作用。近年来随着表观遗传学的发展,为肿瘤的早期检测提供了新的方向。在表观遗传学中DNA甲基化与乳
江苏污泥生产活性炭项目获成功从2006年开始,南京泰联自动化工程技术有限公司与南京大学环境学院王炳坤教授等一起,开始对污泥生产活性炭新技术进行潜心研究,先后在添加活化
期刊
油分在种子中的积累是生物合成的典型范例,其最终产物的多样性和多功能性,使得可通过遗传控制来有目的地提高种子的品质.种子油分含量的自然遗传倾向于低油分方向筛选.而目前
期刊