Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2013年 第50卷 第12期    出版日期:2013-12-15
综述
社会计算:大数据时代的机遇与挑战
孟小峰, 李 勇, 祝建华,
2013, 50(12):  2483-2491.  doi:10.7544/issn1000-1239.2013.20130890
摘要 ( 2250 )   HTML ( 9)   PDF (1674KB) ( 1932 )  
相关文章 | 计量指标
信息技术的飞速发展,特别是物联网、云计算、社交网络、社会媒体以及信息获取技术的进步,数据正以巨大的速度迅速增长和积累,大数据时代已经到来.社会计算作为一种数据密集型科学,在收集和分析数据的广度、深度以及规模上都产生了巨大的影响,社会计算作为一种新的计算范式,产生了一个新的跨学科研究与应用领域,其广阔的研究内容与应用已引起了学术界和工业界的广泛关注.分析了社会计算产生的历史背景及概念、研究现状及大数据带来的机遇,综述了社会计算不同的研究领域,主要有2个发展趋势:一个面向社会科学,包括计算社会科学、计算社会学、社会网络分析等;一个面向技术应用,包括社交应用、娱乐应用、生产应用等,这2种发展趋势同时又相互影响.最后讨论了社会计算研究领域存在的挑战,包括跨学科合作与训练的问题、科学研究中大数据共享问题以及隐私保护.
其他应用技术
在线社会网络共演化的结构推断与预测
王 莉, 程苏琦, 沈华伟, 程学旗,
2013, 50(12):  2492-2503. 
摘要 ( 944 )   HTML ( 2)   PDF (2018KB) ( 845 )  
相关文章 | 计量指标
在线社会网络研究中,关系结构和交互结构的共演化机理是一个十分关键的核心问题,它反映了在线社会网络关系结构变化、行为模式演化及关系结构与交互结构演化的互影响情况,对于社会推荐、网络舆情预警和控制等都具有重要意义.大量交互信息的可见性和真实关系结构的不易见性,使得利用动态交互网络直接推断隐结构和预测未来结构成为当前研究热点,并成为揭示共演化机理的一种途径.从微观尺度对2种重要的社会网络:社会媒体和社交网络中的动态结构推断和预测的研究进展进行了综述.首先对在线社会网络共演化和结构推断及预测进行定义,并对其之间关系进行分析;然后对隐关系强度推断、类型推断、关系结构预测和交互行为预测的关键技术等进行综述和分析,最后对在线社会网络结构推断与预测研究的难点和发展趋势进行分析和展望.
基于结构冗余性校准的在线式社会网络压缩
杨海陆 张健沛 杨 静
2013, 50(12):  2504-2519. 
摘要 ( 406 )   HTML ( 1)   PDF (4190KB) ( 433 )  
相关文章 | 计量指标
随着社交网络、移动互联网等新兴服务的不断涌现,在线社会网络正以前所未有的速度增长并且呈现出极强的演化特性.网络压缩技术能够将大规模网络压缩成规模更小、结构信息更简洁的网络,在数据存储和网络可视化领域发挥着重要作用.现有的压缩算法为了优化压缩损失,重复比对原始网络与压缩网络之间的差异导致过高的时间开销,并且算法仅局限于静态网络,无法满足在线社会网络的演变要求.针对上述问题,提出一种解决演化网络压缩问题的高效算法,首先设计了基于局部化判定的结构合并贡献函数及其快速调整算法,将网络的首次压缩复杂度控制在O(n)到O(mn)之间;其次,设计了一种面向演化网络压缩的动态校准算法,参照网络演化前后拓扑结构的变化,校准前一时刻的压缩表达以避免网络的重复压缩,在满足在线社会网络演变要求的同时提高了压缩效率;最后,通过对真实数据集的实验分析,验证了算法的有效性.
基于链接密度聚类的重叠社区发现算法
朱 牧 孟凡荣 周 勇
2013, 50(12):  2520-2530. 
摘要 ( 1134 )   HTML ( 6)   PDF (3265KB) ( 1046 )  
相关文章 | 计量指标
为了能够更加有效地发现社会网络中具有重叠性的社区结构,提出一种基于链接密度聚类的重叠社区发现算法DBLINK.该算法首先以网络中的边集为对象,将其划分为若干个互不相连的链接社区,再将所得到的链接社区转化为最终的节点社区,隶属于不同链接社区边的交点即为网络中的重叠节点.由于DBLINK采用基于密度的算法对边集进行聚类,将不满足一定条件的边孤立出来,使其不隶属于任何链接社区,因此可以避免社区结构过度重叠的现象发生,从而提高了重叠社区发现的质量.实验结果表明,DBLINK不仅具有较好的时间效率,而且在社区发现的质量方面也优于其他几种代表性的重叠社区发现算法.
位置服务中的社会感知计算方法研究
郭 迟, 方 媛, 刘经南, 万 怡,
2013, 50(12):  2531-2542. 
摘要 ( 787 )   HTML ( 1)   PDF (3305KB) ( 647 )  
相关文章 | 计量指标
随着定位技术尤其是室外定位技术的发展,产生了大量的位置数据.这些数据在一定程度上能够反映出丰富的社会信息,从而使得位置服务向着社会化计算的方向发展.因此位置社会感知计算方法尤为重要.位置服务中的社会感知计算是指通过人类社会生活空间部署的大规模位置传感设备,感知识别社会个体的行为、分析挖掘群体社会交互特征和规律、引导个体社会行为、支持社群的互动、沟通和协作的一种计算技术,是位置服务从单纯的定位服务转变成为具有社会化计算形态的关键.围绕基于位置的社会感知计算相关方法,分别从计算模型和评估手段两方面进行了系统的分类和归纳,重点阐述了3个问题:1)什么是基于位置的社会感知及其计算框架;2)位置的社会性与人类行为的关联关系是什么样的.主要将其划分为感知位置的社会语义、感知人类移动与其社交活动的关系、感知和预测用户的移动行为和感知用户的社会属性4个方面来展开论述;3)在实际分析及系统应用中尤其是面对位置大数据分析时,常用的感知和数据挖掘方法有哪些.
基于社会群体搜索算法的机器人路径规划
冯 翔 马美怡 施 尹 虞慧群
2013, 50(12):  2543-2553. 
摘要 ( 534 )   HTML ( 7)   PDF (2731KB) ( 608 )  
相关文章 | 计量指标
机器人学是现在及未来科技发展的重点,路径规划是机器人学中的一个重要课题.生物界一些群居动物有严格的等级制度和职责分工,受社会群居动物行为启发,提出社会群体搜索算法(social group search algorithm, SGSO).社会群体搜索算法对群体的分类及信息反馈机制——领导-追随机制的制定,降低了早熟的概率,交叉变异和淘汰机制的引入增加了搜索范围,减少了陷入局部最优的可能.同时,对提出的社会群体搜索算法进行了分析,从理论上证明了算法的收敛性;将社会群体搜索算法应用于机器人路径规划进行仿真,从实验中验证了算法的有效性,并与遗传算法和粒子群算法比较,进一步证明了社会群体搜索算法在机器人路径规划问题中的有效性和高效性.
基于词性标注和依存句法的Web金融信息情感计算
万常选 江腾蛟 钟敏娟 边海容
2013, 50(12):  2554-2569. 
摘要 ( 867 )   HTML ( 0)   PDF (2287KB) ( 707 )  
相关文章 | 计量指标
基于词袋模型的文本情感倾向性分析没有考虑句子的句法结构对句子语义的理解,基于依存句法分析的方法试图解决这一问题.目前基于依存句法分析的方法对影响文本情感的依存关系的选择多根据人为观察,带有随意性.根据影响句子情感倾向性的原极性、修饰极性和动态极性,1)找出了影响句子情感倾向性的4种词性:形容词、动词、副词和名词;2)从词性和汉语句子成分理解的角度,逐一分析了24种依存关系对句子情感计算的影响,找出了可能影响句子情感倾向性的8种依存关系;3)根据这8种依存关系中可能的词性组合设计了6种情感计算规则,并提出了基于二叉树的情感计算策略,设计了情感计算二叉树的构建算法和基于情感计算二叉树的情感计算算法;4)在Web金融信息上进行了实验测试,实验结果表明了该方法的有效性.
基于情感特征聚类的半监督情感分类
李素科 蒋严冰
2013, 50(12):  2570-2577. 
摘要 ( 886 )   HTML ( 0)   PDF (1416KB) ( 924 )  
相关文章 | 计量指标
情感分类是观点挖掘的一个重要的方面.提出了一种基于情感特征聚类的半监督式情感分类方法,该方法只需要对少量训练数据实例进行情感类别标注.首先从消费者评论中提取普通分类特征和情感特征,普通分类特征可以用来训练一个情感分类器.然后使用spectral聚类算法把这些情感特征映射成扩展特征.普通分类特征和扩展特征一起通过训练得到另一个情感分类器.2个分类器再从未标签数据集中选择实例放入到训练集合中,并通过训练得到最终的情感分类器.实验结果表明,在同样的数据集上该方法的情感分类准确度比基于self-learning SVM的方法和基于co-training SVM的方法的情感分类准确度要高.
人群拥挤事件中的一种情绪感染仿真模型研究
刘 箴 金 炜 黄 鹏 柴艳杰
2013, 50(12):  2578-2589. 
摘要 ( 818 )   HTML ( 0)   PDF (6356KB) ( 708 )  
相关文章 | 计量指标
随着我国城市化进程的推进,制定人员密集场所的非常规应急预案具有重要的现实意义.在人群拥挤事件发生时,事发人群的行为特征有别于正常的人群,容易导致人群陷入消极情绪.已有的人群仿真方法未能充分考虑人群个体之间的情绪感染,对人群拥挤的极端后果缺少研究.以火车站站台人群拥挤情景为研究对象,采用智能体的思想,提出了个体在情绪影响下的行为描述,根据人群中是否存在管理人员,提出了一种情绪感染计算方法.在计算机上编制了人群情绪感染仿真演示原型系统,对人群中的情绪感染、避碰、跌落等行为实现了三维情景仿真演示.实验结果表明,人群的消极情绪不仅与初始的情绪分布有关,也与管理人员的数量以及分布位置有关,控制人群中的消极情绪感染是避免人群拥挤事件的重要环节.
文化认同及文化版图演化现象的社会计算模型
云 健 刘向东 刘勇奎
2013, 50(12):  2590-2602. 
摘要 ( 635 )   HTML ( 0)   PDF (4322KB) ( 625 )  
相关文章 | 计量指标
文化认同以及由于文化认同感的演变结果与地理边界的不一致性在文化版图上形成的文化侵蚀现象、文化融合现象等文化安全问题是文化领域的核心问题之一.在社会计算方法引入之前,该问题是典型的不能假设、无法进行计算实验的社会科学问题.将社会计算方法引入这一核心问题,使对该问题的实验研究进入到一个无风险的实验空间;运用基于多智能体的人工社会建模技术,确定了若干可刻画跨文化交流或文化内部环境稳定性的计算因子、文化抗消解惯性因子、文化身份状态因子、异族群的智能体间地理距离因子、“安土重迁”心理特征因子及“安土重迁”行为特征因子等;在此基础上,给出了刻画文化认同及其版图边界演变过程中文化侵蚀、文化融合与文化保护等现象的社会计算模型,并进行了大量的社会计算实验.实验结果表明:所选取的各种计算因子都是影响文化认同及其版图演化过程的重要因素,但作用各不相同;文化认同感演化的诸多规律也由该模型得出.该计算模型今后可在各类文化保护方案设计和方案效果评估等实际社会工作中发挥作用.
基于吸收态随机行走的两阶段效用性查询推荐方法
朱小飞 郭嘉丰 程学旗 兰艳艳
2013, 50(12):  2603-2611. 
摘要 ( 619 )   HTML ( 2)   PDF (1632KB) ( 488 )  
相关文章 | 计量指标
搜索引擎已经成为人们获取信息的重要途径,然而对于用户而言如何构造一个合适的查询仍然是一项困难的工作.为了减轻用户搜索信息的负担,查询推荐技术应运而生并且已经成为当今搜索引擎不可或缺的组成部分.传统的查询推荐方法主要关注向用户推荐相关性查询,即推荐与源查询具有相近搜索意图的其他查询.然而查询推荐的根本目标是帮助用户成功完成其搜索任务,而不仅仅是找到相关性查询,尽管相关性查询有时也能得到有用的搜索结果.为了更好地满足用户的搜索目标,一种更直接的查询推荐方式是向用户推荐高效用性查询,即能够更好满足用户信息需求的查询.提出了一个基于吸收态随机行走的2阶段效用性查询推荐方法,该方法能够同时对用户的查询重构行为和查询点击行为进行建模并推导出查询的效用.在真实查询日志上的实验结果表明:新方法在评价指标查询相关率(query relevant ratio, QRR)和平均相关文档数(mean relevant document, MRD)上要显著优于其他5种基准方法.
论文
中文问答系统中时间敏感问句的识别和检索
侯永帅 张耀允 王晓龙 陈清财 王宇亮 户保田
2013, 50(12):  2612-2620. 
摘要 ( 868 )   HTML ( 4)   PDF (1632KB) ( 1998 )  
相关文章 | 计量指标
当前问答系统如“百度知道”、“SoSo问问”等在问句检索时没有考虑时效性要求,对时间敏感问句不能返回满足时效要求的结果.针对该问题,设计了时间敏感问句的识别和检索方法:首先依据时效要求对问句进行分类,识别出时间敏感问句,然后解析时间敏感问句的时效区间,最后根据解析结果对问句检索结果进行过滤,得到满足时效要求的结果.问句分类采用词法、句法和语义等特征,使用决策树、朴素贝叶斯、SVM等机器学习方法进行测试.问句的时效区间使用构造的时间域表达式计算获得.实验表明,使用C5.0决策树进行时间敏感问句的识别准确率达到0.901;与未考虑时间敏感问题的系统相比,时间敏感问句检索结果平均精度得到较大改善.
搜索引擎广告中广告商状态建模
姜昌浩, 张 敏, 高 斌, 刘奕群, 马少平,
2013, 50(12):  2621-2628. 
摘要 ( 391 )   HTML ( 0)   PDF (1673KB) ( 476 )  
相关文章 | 计量指标
搜索引擎广告是目前互联网上一种非常成功的商业模式,它已成为搜索引擎公司的主要收入来源并为广告商们提供了许多商机.搜索引擎、广告商和搜索用户构成了搜索引擎广告的3个主要组成部分——搜索引擎提供技术和服务、广告商提供广告内容、用户浏览并点击广告.其中搜索引擎相关技术以及用户行为都有比较多的研究和成型的技术,但对广告商尤其是广告商状态的研究却并不多见.基于此背景,对搜索引擎广告中广告商的状态进行了深入的研究.在方法上按照广告商相关广告的展示次数、点击次数以及广告费用来对其潜在状态进行描述和划分,并使用隐Markov模型对广告商的时序状态进行建模.重点在于将机器学习和数据挖掘的方法应用于广告商的建模之中,并取得了不错的预测正确率.
案例索引BCS-Tree及其构建方法研究
范海雄 刘付显 夏 璐
2013, 50(12):  2629-2641. 
摘要 ( 366 )   HTML ( 0)   PDF (5016KB) ( 413 )  
相关文章 | 计量指标
为克服现有案例索引方法存在的不足,提出了一种新的索引结构BCS-Tree.首先,对松弛聚类(graph-based relaxed clustering, GRC)算法进行了自适应改进,以克服现有基于聚类方法受初值影响大、只能适应凸形聚类等缺点;其次,将KICA与最小外接矩阵(minimum bounding rectangle, MBR)结合,增强了MBR方法对非线性和非正态分布数据的处理能力;然后,在给出双基点选择方法的基础上,提出了基于改进GRC和双基点聚类分割的BCS-Tree构建方法;最后,基于对查询点和案例数据之间可能分布关系的全面分析,设计了BCS-Tree的查询算法,并结合理论推导和实例验证,对BCS-Tree及其查询算法进行了分析.结果证明,所提的索引构建方法具有较强的参数鲁棒性和适用性,且BCS-Tree及其查询算法具有良好的检索效能.
基于概率生成模型的网络数据分类方法
王桢文 肖卫东 谭文堂
2013, 50(12):  2642-2650. 
摘要 ( 630 )   HTML ( 2)   PDF (2131KB) ( 457 )  
相关文章 | 计量指标
利用实体之间的相互关系来对实体进行分类的网络数据分类是数据挖掘的一个重要研究内容.现有的网络数据分类方法普遍根据邻居节点的类别来对节点进行分类.这些方法在同质性程度较高的网络中达到了很高的分类精度.然而在现实世界中,存在许多同质性程度很低的网络.在低同质性网络中,大多数相连节点的类别不同,所以现有方法难以正确预测出节点的类别.因此,提出了一种新的网络数据分类方法.其主要思路是建立一个描述网络的概率生成模型.在这个概率生成模型中,将网络中的边作为观察变量,将未知类别节点的类别作为潜在变量.通过吉布斯采样方法对模型进行求解,计算出潜在变量的取值,从而得到未知类别节点的类别.在真实数据集上的对比实验表明,提出的分类方法在低同质性网络上有更好的分类性能.
云环境中基于cache共享的虚拟机同驻检测方法
余 思, 桂小林, 张学军, 林建财, 王君飞,
2013, 50(12):  2651-2660. 
摘要 ( 818 )   HTML ( 0)   PDF (2553KB) ( 451 )  
相关文章 | 计量指标
云计算是一种新型计算模型,按需提供外包计算和存储服务,具有资源共享、多租户服务等特性.但是,它也面临着新的安全威胁,例如侧通道攻击.通过侧通道攻击,恶意用户可以突破虚拟机隔离性,以一种隐蔽的方式获取其他用户的私密信息.现有侧通道攻击方法缺乏对其他同驻虚拟机干扰的分析.然而,这种干扰在多租户云环境中是不可避免的.针对该问题,提出一种基于cache侧通道攻击的虚拟机同驻检测方法.该方法基于期望和熵分析了cache负载特征,采用基于聚类的方法提取cache负载特征,通过同驻检测策略实现虚拟机同驻检测.实验结果表明,该方法能够有效地提取cache负载特征,并以较高的成功率实现虚拟机同驻检测.同时进一步表明,侧通道攻击是云计算面临的一种重要安全挑战.
基于符号执行和LTL公式重写的测试用例产生方法
陈冬火, 刘 全,
2013, 50(12):  2661-2675. 
摘要 ( 797 )   HTML ( 0)   PDF (2853KB) ( 463 )  
相关文章 | 计量指标
基于模型检验等形式化方法的测试用例自动产生技术成为测试自动化领域一项重要的进展.对于输入和输出为无界抽象数据类型的无限状态系统,利用传统模型检验技术难以有效地产生测试用例集合,提出基于符号执行和公式重写的测试用例产生方法.通过建立程序的符号化执行模型,避免输入和输出变量数值化枚举而导致的无限状态系统的建模和状态爆炸问题;建立基于符号化执行模型的时序公式重写规则,并根据线性时序逻辑(linear temporal logic, LTL)公式的反例模式求取复杂属性及行为约束关系,利用约束求解的方法自动产生测试用例集合.这种方法集成了符号执行技术和时序公式状态重写——一种轻量级模型检验技术,成为基于复杂抽象数据类型系统与属性相关的测试用例自动产生的有效方法.
带参数的共递归操作及其计算律
苏锦钿, 余珊珊,
2013, 50(12):  2676-2690. 
摘要 ( 444 )   HTML ( 0)   PDF (1780KB) ( 389 )  
相关文章 | 计量指标
针对共归纳数据类型上的unfold无法描述带参数的共递归操作的问题,证明了笛卡儿封闭范畴上的有限扩展多项式函子的终结共代数在固定参数和累积参数下都是强终结的,并利用该强终结性给出强共归纳数据类型的定义以及带固定参数和累积参数的共递归操作——punfold和aunfold,从而将Pardo对强归纳数据类型及带参数的递归计算pfold和afold的研究扩展到共归纳数据类型上,使得unfold可直接包含额外的参数用于作为计算的输入或者保存临时的计算结果,避免采用高阶函数的方式.从范畴论的角度给出punfold和aunfold的各种性质、计算律及在函数式程序语言Haskell中的实现,并指出它们在程序推导、转换和优化中的应用.
概率有限状态自动机的代数性质
谢正卫, 翟 莹, 邓培民, 易 忠,
2013, 50(12):  2691-2698. 
摘要 ( 682 )   HTML ( 1)   PDF (696KB) ( 548 )  
相关文章 | 计量指标
利用矩阵、同态、同构、同余等代数工具研究概率有限状态自动机的代数性质.首先定义了输入集上两个字符串同余的概念,并利用概率转移矩阵给出2个字符串同余的一些等价刻画.进而提出概率有限状态自动机同态和同构的概念,并给出了概率有限状态自动机同态定理.证明了2个概率有限状态自动机同构的充要条件是它们的概率转移矩阵可以通过第1种行列初等变换相互转化;同时提出了2个概率有限状态自动机积与和的概念,并得到了积自动机、和自动机的同态关系.最后将模糊自动机中交换的概念引入到概率有限状态自动机中,并利用概率转移矩阵给出了此类自动机交换的一些等价刻画以及和自动机、积自动机交换的充要条件.
高级AC自动机的快速构建方法
范洪博, 姚念民,
2013, 50(12):  2699-2706. 
摘要 ( 537 )   HTML ( 1)   PDF (1397KB) ( 436 )  
相关文章 | 计量指标
高级AC(advanced AC, AAC)是一种基于自动机的多模式串匹配算法,应用极为广泛.在大规模匹配时AAC自动机构建耗时较大.改进了经典精确单模式匹配算法——DFA算法自动机构建过程,并将其扩展到多模式匹配领域,提出Set DFA自动机,并证明Set DFA自动机和AAC自动机一致.该自动机构建方法简单清晰,无需计算失败函数,自动机内每个状态在生成后只需访问一次即可完成自动机构建.实验表明Set DFA构建时间只有AAC自动机的一半左右.