新浪微博snow ball采样算法偏差研究(英文)

随着在线社交网络的广泛应用,多种多样的采样算法应用于在线社交网络结构和特性的建模和分析。本文首先对这些常用的在线社交网络采样算法做分类对比,然后对应用相对广泛的snow ball采样算法进行深入研究。本文通过对国内最早、应用最广泛的在线社交网络新浪微博的数据进行采样分析,研究新浪微博网络结构的特点,验证得出数据量不足会导致在线社交网络的网络半径和度分布产生较大偏差。     

在线社交网络的UNI64采样方法

在对社交网络采样方法进行研究时,常以拒绝-接受采样法得到的样本作为对照来评价其他采样方法的优劣.由于各种在线社交网络陆续将其用户ID系统由32位升级为64位,导致拒绝-接受采样法的采样命中率近乎为零.本文根据在线社交网络的特点,以新浪微博为例,对其用户ID分布情况进行分析,提出了一种改进的拒绝-接受采样法UNI64.该方法通过分析网络有效ID样本的分布情况,结合聚类的方法将整个样本空间划分为有效区间和无效区间,并使采样算法避开无效区间,仅在有效区间内生成待测样本,从而有效提高了拒绝-接受采样法在有效样本极为稀疏的样本空间内采样的命中率.     

融合重叠社区正则化及隐式反馈的协同过滤方法

针对目前推荐系统存在的数据稀疏和冷启动等问题,提出了一种融合重叠社区正则化及隐式反馈的协同过滤方法（OCRIF）,该方法不仅考虑了用户在社交网络中的社区结构,而且将用户评分信息与社交信息的隐式反馈融入推荐模型之中。此外,由于网络表示学习可以有效学习节点在社交网络的全局结构上的近邻信息,提出了一种网络表示学习增强的OCRIF（OCRIF+）,该方法结合社交网络中用户在网络中的低维表示与用户-商品特征,能更有效地刻画用户之间的相似度及用户对兴趣社区的归属度。多个真实数据集上的实验结果显示：所提出的方法的推荐效果优于同类方法,与TrustSVD方法相比,在FilmTrust、DouBan以及Ciao数据集上,该方法的均方根误差（RMSE）分别下降了2.74%、2.55%以及1.83%,平均绝对误差（MAE）分别下降了3.47%、2.97%以及2.40%。     

深度学习的快速磁共振成像及欠采样轨迹设计

目的 快速成像一直是磁共振成像（MRI）技术中的焦点之一,现有多通道并行成像和部分k空间数据重建都是通过减少梯度编码步数来降低数据的获取时间,两者结合起来更能有效地提高扫描速度。然而,在欠采样倍数加高的情况下,依然有很严重的混叠伪影,因此研究一种在保证成像精度的前提下加快成像速度的方法尤为重要。方法 基于卷积神经网络的磁共振成像（CNN-MRI）方法利用大量现有的全采样多通道数据的先验信息,设计并线下训练一个深度卷积神经网络,学习待重建图像与全采样图像之间的映射关系,从而在线上成像时,欠采样所丢失数据能被训练好的网络进行预测。本文探讨了对于深度学习磁共振成像的可选择性欠采样方式,提出了一种新的欠采样轨迹方案。为了判断本文方法的性能,用峰值信噪比（PSNR）、结构相似度（SSIM）以及均方根差（RMSE）来作为衡量的指标。结果 实验结果表明,所提出欠采样方案的综合性能要优于传统欠采样轨迹,PSNR要高出12 dB,SSIM高出近0.1,RMSE要降低0.020.04左右。此外重建结果还与经典的并行重建方法GRAPPA（geneRalized autocalibrating partially parallel acquisitions）、SPIRiT（iterative self-consistent parallel imaging reconstruction from arbitrary k-space）以及SAKE（simultaneous autocalibrating and k-space estimation）作比较,从视觉效果以及各项量化指标得出本文方法能重建出更准确的结果,并且重建速度要快5倍以上。结论 深度学习方法能很好地在线下训练时从大量数据集中提取并学习到有价值的先验信息,所以在线上测试时能在较短时间内重建出优于经典算法的高质量结果;提出的1维低频汉明滤波欠采样方案则有利于提升该网络的性能。     

基于强社交图的多约束信任图模式增量匹配算法

针对现有的图匹配方法没有考虑到社交背景下的多种约束以及在多约束图匹配中图结构的变化,提出一种多约束图模式匹配方法.为了提高多约束图模式匹配的效率,提出强社交图的概念及一种强社交图的索引结构来索引图的可达性、图模式和上下文背景信息,提出维护强社交图索引的算法INC-SSG和多约束图匹配的增量算法SSG-IncMGPM,当面对强社交图结构的变化时能快速有效地识别多约束图模式匹配结果.通过对五个真实社交图的实证研究,验证了该方法在效率和有效性方面的优越性.     

信任社交网络中基于图熵的个性化推荐算法

随着社交网络的飞速发展引起了人们对推荐系统（RS）的广泛关注。针对社交网络中现有推荐方法仍存在冷启动问题以及未考虑用户所处的社交网络信息的情况，提出了在信任社交网络中基于图熵的个性化推荐算法（PRAGE）。首先，根据用户物品和它们之间的反馈信息建立用户物品图（UIG），同时引入信任机制建立用户信任图（UTG）；其次，通过对两个图使用随机游走算法得到用户与物品的初始相似度和基于信任机制的新的用户物品相似度；重复随机游走过程直至相似度稳定到收敛值；然后，使用UIG和UTG的图熵对两组相似度进行加权并最终相应地得出目标用户的最终推荐列表。在真实的数据集Epinions和FilmTrust上的实验结果表明，相比经典的基于随机游走算法，PRAGE的精确率分别提高了34.7%和19.4%，召回率分别提高了28.9%和21.1%，能够有效地缓解推荐的冷启动问题且在精确率和覆盖率指标上均优于对比算法。     

高效二阶注意力对偶回归网络的超分辨率重建

针对中间层通道特征相关性利用率低、低分辨率图像和高分辨率图像函数映射空间非线性的问题,提出了一种基于高效二阶注意力机制的对偶回归网络（ESADRNet）。该网络将重建任务分为两个回归网络：原始回归网络和对偶回归网络。原始回归网络采用FReLU为激活函数的下采样层对图像进行更高效的空间上下文特征提取;基于多级跳跃连接残差块（MLSCR）和高效二阶通道注意力模块（ESOCA）构成的多级跳跃连接残差注意力模块（MLSCRAG）、共享源跳跃连接（SSC）和亚像素卷积构建渐进式上采样网络,使网络专注于更具辨别性的特征表示,具有更强大的特征表达和特征相关学习能力;利用对偶回归网络约束映射空间,寻找最优重建函数。在Set5、Set14、BSD100和Urban109数据集上经过对比实验证明,该网络在客观定量指标和主观视觉方面均优于其他对比方法。     

复杂网络中的在线社交网络演化模型

在线社交网络是一种广泛存在的社会网络,其节点度遵循幂率分布规律,但对于其结构演化模型方面的相关研究还不多。基于复杂网络理论研究在线社交网络内部结构特征,提出一种结合内增长、外增长及内部边更替的演化模型,借助平均场理论分析该模型的拓扑特性,实验和理论分析表明由该模型生成的网络,其度分布服从幂率分布,且通过调整参数,幂率指数在1~3,能较好地反映不同类型的真实在线社交网络的度分布特征,因此具有广泛适用性。     

面向主题的社交网络采集技术

社交网络数据采集是开展社交网络分析的基础.针对当前面向主题的社交网络数据采集技术采集数据少、召回率低的问题,本文提出基于内置搜索引擎和基于通用搜索引擎相结合的主题消息采集方法,并将LDA（Latent Dirichlet Allocation,隐含狄利克雷分布）模型应用于主题关键词的迭代扩展,并提出了一种基于用户生存值的高效扩展策略.实验结果表明本文提出的方法可以使面向主题的社交网络数据采集系统在保证一定准确率的情况下进一步获取主题相关数据.     

基于深度特征融合的无纺布低对比度浆丝缺陷检测方法

针对无纺布生产过程中产生的浆丝缺陷对比度较低,以及传统图像处理方法对其检测效果较差的问题,提出了一种基于卷积神经网络（CNN）的无纺布低对比度浆丝缺陷检测方法。首先,对采集到的无纺布图像进行预处理以构建浆丝缺陷数据集;然后,利用改进的卷积神经网络以及多尺度特征采样融合模块构造编码器以提取低对比度浆丝缺陷的语义信息,并在解码器中采用跳跃连接进行多尺度特征融合来优化上采样模块;最后,通过所构建的数据集训练网络模型,从而实现低对比度浆丝缺陷的检测。实验结果表明,所提方法可以有效定位并检测出无纺布上的低对比度浆丝缺陷,其平均交并比（MIoU）、类别平均像素准确率（MPA）分别可以达到77.32%和86.17%,单张样本平均检测时间为50 ms,能够满足工业生产的要求。     

Finding Minimum Vertex Covering in Stochastic Graphs: A Learning Automata Approach

Structural and behavioral parameters of many real networks such as social networks are unpredictable, uncertain, and have time-varying parameters, and for these reasons, deterministic graphs for modeling such networks are too restrictive to solve most of the real-network problems. It seems that stochastic graphs, in which weights associated to the vertices are random variables, might be better graph models for real-world networks. Once we use a stochastic graph as the model for a network, every feature of the graph such as path, spanning tree, clique, dominating set, and cover set should be treated as a stochastic feature. For example, choosing a stochastic graph as a graph model of an online social network and defining community structure in terms of clique, the concept of a stochastic clique may be used to study community structures’ properties or define spreading of influence according to the coverage of influential users; the concept of stochastic vertex covering may be used to study spread of influence. In this article, minimum vertex covering in stochastic graphs is first defined, and then four learning, automata-based algorithms are proposed for solving a minimum vertex-covering problem in stochastic graphs where the probability distribution functions of the weights associated with the vertices of the graph are unknown. It is shown that through a proper choice of the parameters of the proposed algorithms, one can make the probability of finding minimum vertex cover in a stochastic graph as close to unity as possible. Experimental results on synthetic stochastic graphs reveal that at a certain confidence level the proposed algorithms significantly outperform the standard sampling method in terms of the number of samples needed to be taken from the vertices of the stochastic graph.     

二进制递归网络的连通性

二进制递归网络是超立方体的一类特殊变体,它具有很多良好的网络特性。网络的连通性是衡量网络结构通信能力的一个重要性能,虽然到目前为止已知的一些二进制递归网 络的连通性都已被研究过,但这些研究只是针对个体进行的,并不能代表所有二进制递归网络的连通特性。本文通过证明任何一个二进制递归网络中的每对顶点之间只能存在在”条顶点不交路,得到了整个二进制递归网络的点和边连通度皆为”的重要结论。     

无线传感器网络1点和2点连通可靠性研究

无线传感器网络集成了传感器、微机械电子和网络通讯技术,它的巨大应用前景引起了军事部门、工业界和学术界的广泛关注.它的节点不是预先安置,而是随机撒放,那么就有问题:在假定每个传感器节点通讯半径一定,一个固定区域要抛撒多少节点才能保证这些节点组织的网络基本连通?要抛撒多少节点才能保证满足2点间的连通可靠性.本文进行了大量的计算机模拟试验,采用了随机抛撒节点,然后进行连通度测试的方法,给出了节点数、通讯半径和连通关系的曲线簇.通过对曲线簇的对数变换和对变换后曲线簇的回归分析,给出了仿真区间内的单点连通和二点连通的经验公式,取得了满意的效果.给出了通过几何变换可能推广任意通讯半径的方法.本文同时给出了在仿真中的重要参数:随机抛撒均匀分布的节点的邻居节点的分布规律,抛撒后节点满足通讯半径要求建立的连接数的分布规律.这些直接指导无线传感器网络的节点个数和通讯半径选择,连通可靠性设计.     

Exploring networks with traceroute-like probes: Theory and simulations

Mapping the Internet generally consists in sampling the network from a limited set of sources by using traceroute-like probes. This methodology, akin to the merging of different spanning trees to a set of destination, has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sampled graph which sharply differ from the original ones. In this paper, we explore these biases and provide a statistical analysis of their origin. We derive an analytical approximation for the probability of edge and vertex detection that exploits the role of the number of sources and targets and allows us to relate the global topological properties of the underlying network with the statistical accuracy of the sampled graph. In particular, we find that the edge and vertex detection probability depends on the betweenness centrality of each element. This allows us to show that shortest path routed sampling provides a better characterization of underlying graphs with broad distributions of connectivity. We complement the analytical discussion with a throughout numerical investigation of simulated mapping strategies in network models with different topologies. We show that sampled graphs provide a fair qualitative characterization of the statistical properties of the original networks in a fair range of different strategies and exploration parameters. Moreover, we characterize the level of redundancy and completeness of the exploration process as a function of the topological properties of the network. Finally, we study numerically how the fraction of vertices and edges discovered in the sampled graph depends on the particular deployements of probing sources. The results might hint the steps toward more efficient mapping strategies.     

一种保持结点可达性的高效社会网络图匿名算法

为了保护社会网络隐私信息,提出了多种社会网络图匿名化技术.图匿名化目的在于通过图修改操作来防止隐私泄露,同时保证匿名图在社会网络分析和图查询方面的数据可用性.可达性查询是一种基本图查询操作,可达性查询精度是衡量图数据可用性的一项重要指标.然而,当前研究忽略了图匿名对结点可达性的影响,导致较大的可达性信息损失.为了保持匿名图中结点的可达性,提出了可达性保持图匿名化（reachability preserving anonymization,简称RPA）算法,其基本思想是将结点进行分组并采取贪心策略进行匿名,从而减少匿名过程中的可达性信息损失.为了保证RPA算法的实用性,针对其执行效率进行优化,首先提出采用可达区间来高效地评估边添加操作所导致的匿名损失;其次,通过采用候选邻居索引,进一步加速RPA算法对每个结点的匿名过程.基于真实社会网络数据的实验结果表明了RPA算法的高执行效率,同时验证了生成匿名图在可达性查询方面的高精度.     

Local Community Detection Using Link Similarity

Exploring local community structure is an appealing problem that has drawn much recent attention in the area of social network analysis.As the complete information of network is often difficult to obtain,such as networks of web pages,research papers and Facebook users,people can only detect community structure from a certain source vertex with limited knowledge of the entire graph.The existing approaches do well in measuring the community quality,but they are largely dependent on source vertex and putting too strict policy in agglomerating new vertices.Moreover,they have predefined parameters which are difficult to obtain.This paper proposes a method to find local community structure by analyzing link similarity between the community and the vertex.Inspired by the fact that elements in the same community are more likely to share common links,we explore community structure heuristically by giving priority to vertices which have a high link similarity with the community.A three-phase process is also used for the sake of improving quality of community structure.Experimental results prove that our method performs effectively not only in computer-generated graphs but also in real-world graphs.     

星网的4-限制边连通度

星网是并行与分布式处理系统中最流行的互连网络之一,它以n维星图作为拓扑结构。k-限制边连通度是衡量网络可靠性的重要参数之一;一般地,网络的k-限制边连通度越大,它的连通性就越好。研究了星网的k-限制边连通度,证明了当n≥4时,n维星网的4-限制连通度为4n－10。     

星型网络的3-限制边连通性

星型互连网络是并行与分布式处理领域中最流行的互连网络之一,它以n维星图作为拓扑结构。k-限制边连通度是衡量网络的可靠性的参数之一。一般来说,一个网络的k-限制边连通度越大,其连通性就越好。研究了星型互连网络的k限制边连通度;证明了当n≥3时,n维星型互连网络的3-限制连通度为3n－7。     

边收缩池化的网格变分自编码器

目的 3D形状分析是计算机视觉和图形学的一个重要研究课题。虽然现有方法使用基于图的卷积将基于图像的深度学习推广到3维网格,但缺乏有效的池化操作限制了其网络的学习能力。针对具有相同连通性,但几何形状不同的网格模型数据集,本文利用网格简化的边收缩操作建立网格层次结构,提出了一种新的网格池化操作。方法 本文改进了传统的网格简化方法,以避免生成高度不规则的三角形,利用改进的网格简化方法定义了新的网格池化操作。网格简化的边收缩操作建立的网格层次结构之间存在对应关系,有利于网格池化的定义。新定义的池化操作有效地编码了层次结构中较粗糙和较稠密网格之间的对应关系。最后提出了一种带有边收缩池化和图卷积的变分自编码器（variational auto-encoder,VAE）结构,以探索3D形状的隐空间并用于3D形状的生成。结果 由于引入了新定义的池化操作和图卷积操作,提出的网络结构比原始MeshVAE需要的参数更少,因此可以处理更稠密的网格模型。结论 实验表明提出的方法具有更好的泛化能力,并且在各种应用中更可靠,包括形状生成、形状插值和形状嵌入。     

Clustering large attributed information networks: an efficient incremental computing approach

In recent years, many information networks have become available for analysis, including social networks, road networks, sensor networks, biological networks, etc. Graph clustering has shown its effectiveness in analyzing and visualizing large networks. The goal of graph clustering is to partition vertices in a large graph into clusters based on various criteria such as vertex connectivity or neighborhood similarity. Many existing graph clustering methods mainly focus on the topological structures, but largely ignore the vertex properties which are often heterogeneous. Recently, a new graph clustering algorithm, SA-cluster, has been proposed which combines structural and attribute similarities through a unified distance measure. SA-Cluster performs matrix multiplication to calculate the random walk distances between graph vertices. As part of the clustering refinement, the graph edge weights are iteratively adjusted to balance the relative importance between structural and attribute similarities. As a consequence, matrix multiplication is repeated in each iteration of the clustering process to recalculate the random walk distances which are affected by the edge weight update. In order to improve the efficiency and scalability of SA-cluster, in this paper, we propose an efficient algorithm In-Cluster to incrementally update the random walk distances given the edge weight increments. Complexity analysis is provided to estimate how much runtime cost Inc-Cluster can save. We further design parallel matrix computation techniques on a multicore architecture. Experimental results demonstrate that Inc-Cluster achieves significant speedup over SA-Cluster on large graphs, while achieving exactly the same clustering quality in terms of intra-cluster structural cohesiveness and attribute value homogeneity.