支持隐私保护的社交网络信息传播方法

社交网络影响力传播重点关注如何使用少量的种子集合在社交网络中产生尽可能高的影响力,并将转发作为信息传播的唯一方式,忽略了其他传播方式,例如用户可通过发布一条与所见信息内容相似的信息来进行传播,这种传播方式(称为转述)因为难以追踪,所以存在隐私泄漏的风险。针对上述问题,定义了一种支持转述关系的社交网络信息传播模型,提出了一种支持用户隐私保护的信息传播方法 LocalGreedy,确保用户发送的信息不泄漏到指定黑名单的同时,最大化传播产生的影响力,平衡了隐私保护和信息传播的矛盾。针对种子集合选取的枚举问题,提出了支持隐私保护的递增策略构造种子集合,减少时间开销;给出了计算节点的局部影响子图方法,快速估计种子集合传播产生的影响力;为确保种子集合满足隐私保护约束限制,提出了推导节点泄漏态概率上限的方法,避免使用蒙特卡洛方法产生的时间开销。使用爬取的新浪微博数据集进行实验验证和实例分析,结果表明了所提方法的有效性。     

基于社区发现的社交网络影响力阻断最大化算法北大核心CSCD

随着社交网络的日益普及,社交网络已经成为信息传播的主要平台之一。由于对社交网络内容监管相对困难,导致一些负面信息容易快速扩散并产生较大的不良影响。影响力阻断最大化问题旨在寻找需要采用正影响的节点集,使信息传播过程中被负向消息影响的节点数量最小化。针对现有社交网络影响力阻断算法运行时间复杂度较高的问题,文章提出了基于社区发现的影响力阻断最大化算法,该算法首先使用社交网络节点的扩展h指数中心性来选择候选种子节点;然后以这些种子节点为起点,利用标签传播算法发现社交网络中的社区;接着通过计算社交网络社区的关系矩阵及当前关系矩阵的模块度对社区进行合并;最后,计算初始种子节点的标签度量等级,选取前k个节点作为具有最大阻断影响力的成员。实验结果表明,该算法阻断性能好,且时间复杂度低。     

有限节点驱动的微博社会网络话题推荐方法

针对微博在线社会网络中的话题推荐问题,研究了如何选取多个驱动用户节点使得推荐话题能够得到大的传播广度,提出了一种新的信息推荐方法,可以求得次优的驱动节点集合使得推荐话题得到近似最大的传播广度。通过三个环节进行计算：通过修正的PageRank算法求得影响力大的节点;计算第一步得到的每个节点引起的话题传播广度;计算多个节点联合驱动时话题传播的广度,选择使传播广度最大的驱动节点集合。实验结果表明选取的近似最优驱动节点集合能够使得推荐信息得到更大广度的传播。     

基于MRLT模型多关系社交网络影响力最大化研究

社交网络影响力最大化问题是基于特定的传播模型,在网络中寻找一组初始传播节点集合,通过其产生最终传播影响范围最大的一种最优化问题。已有的相关研究大多只是针对单关系社交网络,即在社交网络中只存在一种关系。但在现实中,社交网络的用户之间往往存在着多种关系,并且这多种关系共同影响着网络信息传播及其最终影响范围。在线性阈值模型的基础上,结合网络节点间存在的多种关系,提出MRLT传播模型来建模节点间的影响力传播过程,在此基础上提出基于反向可达集的MR-RRset算法,解决了传统影响力最大化问题研究过程中由于使用贪心算法所导致的计算性能较低的问题。最后通过在真实数据集上的实验对比,表明所提方法具有更好的影响力传播范围及较大的计算性能提升。     

基于图结构特征分析的Top-k结构洞发现算法

结构洞通常指社交网络中处于信息扩散关键位置的节点,此类节点对社交网络舆情控制、影响力分析、信息传播等具有重要作用。为快速准确地找到社交网络中的结构洞,提出一种基于图最短路径增量的Top-k结构洞发现算法。通过计算并分析节点的图最短路径增量、连通分量个数和节点方差确定其结构洞属性值,并依据该属性值对节点进行排序,从而发现Top-k结构洞。同时,结合中介中心性算法进行节点的过滤与筛选,大幅降低算法的时间复杂度。在真实网络和不同规模LFR人工合成网络上的实验结果表明,与经典结构洞发现算法相比,该算法具有更高的结构洞检测效率。     

一种兴趣驱动的跨网络传播优化算法

现有社交网络影响力优化算法难以发现跨多个社交网络的全局影响力最大节点.对此,利用用户兴趣和跨网络重叠用户对多个社交网络进行研究,提出一种兴趣驱动的跨网络传播模型,设计跨网络影响力的优化算法.实验结果表明,相比现有算法,该算法仅用1/5的种子节点就能达到相同的影响力效果,同时计算时间开销减少了6/7.     

属性和亲密度关系兼顾的影响力研究

随着5G的发展,网络传播以前所未有的速度向各领域渗透.其中,影响力分析是研究网络信息传播机制的关键技术.传统的影响力分析算法主要通过选取具有最大传播特性的种子节点用于网络传播.但在种子节点选取上,其度量算法没有反映社交网络中的潜在信息.这将对影响力传播分析造成影响,同时一旦社交网络结构遭到破坏,网络的传播能力将会受到影响.针对这一问题,本文首先定义了一种基于属性的朋友亲密度度量关系,量化网络中各用户的影响力;其次,提出了一种属性和亲密度兼顾的影响力算法,该算法综合考虑了网络的结构、属性和亲密度三者之间的关系,选择出具有高影响力及抗攻击性的种子节点,提高网络传播能力及抗攻击能力;最后,通过真实网络环境下的实验,验证出相比现有的度量算法,本文提出的算法在种子节点数目较大时具有更好的传播特性,并且在隐私高风险状态下的社交网络中,该算法的受攻击影响程度稳定在5%-10%左右,影响程度最低,具有较好的抗攻击性.     

基于局部域的影响力最大化算法

用户影响力度量是影响力最大化问题的核心,与网络拓扑结构相关的影响力度量指标主要分为全局性指标和局部性指标,其中全局性指标需要依靠网络完整拓扑结构计算节点影响力且时间复杂度较高,局部性指标通常忽略或弱化了网络中的自环和多边现象,导致对节点影响力的度量不全面,限制信息最终传播范围。结合三度分隔原理,提出基于局部域的影响力最大化算法。考虑网络中的自环和多边现象,根据网络拓扑结构构建生成图。依据生成图划分每个节点对应的局部域,使用节点在局部域内的影响力近似其在全局范围内的影响力,并据此选择候选种子节点。计算候选种子加入种子集合后的重叠比因子,根据重叠比因子决定是否将此候选种子节点选作种子节点,控制种子集合的影响力重叠程度。在真实数据集上的实验结果表明,与MaxDegree、PageRank等算法相比,该算法能有效识别高影响力节点群体,扩大信息传播范围,且具有较低的时间复杂度。     

基于3-layer中心度的社交网络影响力最大化算法

社交网络影响最大化问题是指如何寻找网络中有限的初始节点,使得影响的传播范围最广。一些贪心算法可以得到较好的影响范围,但是因时间复杂度太高而不适用于大型社交网络。基于度中心性的启发式算法简单但准确度不高;基于介数中心性、接近中心性等全局指标的启发式算法可以较好地识别影响力最大的节点,但计算复杂度也过高。考虑网络节点深层次结构对影响扩散的作用并权衡计算复杂度与准确度,定义了3-layer局部中心度,以计算节点的潜在影响力值。基于线性阈值模型,启发选择一部分种子节点:每一次都选取潜在影响力最大的节点作为种子节点进行激活;运用贪心算法选取剩下的一部分种子节点:每一次都选取具有最大影响增量的节点作为种子节点进行激活。实验表明,该混合算法具有很好的激活范围以及非常低的时间复杂度。     

融合行为和语义的节点影响力分析

社交网络中节点影响力研究在信息传播、舆情监督、社会化商务等领域有重要作用。提出融合行为和语义的节点影响力分析方法--BSA（Behavior and Semantics Analysis）方法。该方法先通过基于Cox模型的时间衰减行为矩阵方法计算受者行为影响力,然后通过语义分析方法计算施者行为影响力,最后融合施者行为影响力与受者行为影响力来计算节点的影响力。仿真实验表明,提出的方法可以较真实地反映社交网络中节点的影响力。     

代价约束下基于随机游走的负影响力传播抑制方法

在社交网络的信息传播机制中,不同用户之间信息扩散往往会受到用户之间影响力的影响,因此开展复杂网络分析研究显得格外必要.首先研究在代价约束下,社交网络的影响力传播模型,在未知网络传播原理的情况下,研究如何利用叠加的随机游走策略对网络的影响力传播进行度量,将影响力传播的范围控制在某一子图中,设计出抑制负影响力传播的有效方法...     

基于影响路径的个性化影响最大化算法

个性化影响最大化问题是近年来社交网络影响最大化问题研究领域一个较新的分支,其现有解决方案普遍建立在网络边影响传播强度一致的假设下,该假设对于真实社交网络缺乏普遍适用性。为此基于独立级联模型,提出最大影响路径算法(MIPA)。该算法通过三个阶段来求解个性化影响最大化问题,首先将边影响强度作对数转换以获得最大影响路径,从而计算网络节点对目标节点的邻居节点的影响;然后利用多条经过目标节点邻居的最大影响路径联合计算目标节点受到的影响强度;最后选择Top-k节点作为种子节点,从而摆脱边影响强度的一致性约束,获取高质量的种子集。在不同的真实社交网络数据集上进行的对比实验验证了算法的有效性。     

Critical Density for Coverage and Connectivity in Three-Dimensional Wireless Sensor Networks Using Continuum Percolation

Although most of the studies on coverage and connectivity in wireless sensor networks (WSNs) considered two-dimensional (2D) settings, such networks can in reality be accurately modeled in a three-dimensional (3D) space. The concepts of continuum percolation theory best fit the problem of connectivity in WSNs to find out whether the network provides long-distance multihop communication. In this paper, we focus on percolation in coverage and connectivity in 3D WSNs. We say that the network exhibits a coverage percolation (respectively, connectivity percolation) when a giant covered region (respectively, giant connected component) almost surely spans the entire network for the first time. Because of the dependency between coverage and connectivity, the problem is not only a continuum percolation problem but also an integrated continuum percolation problem. Thus, we propose an integrated-concentric-sphere model to address coverage and connectivity in 3D WSNs in an integrated way. First, we compute the critical density lambda_C ^con above which coverage percolation in 3D WSNs will almost surely occur. Second, we compute the critical density lambda_c ^con above which connectivity percolation in 3D WSNs will almost surely occur. Third, we compute the critical density lambda_c ^cov-con above which both coverage and connectivity percolation in 3D WSNs will almost surely occur. For each of these three problems, we also compute their corresponding critical network degree. Our results can be helpful in the design of energy-efficient topology control protocols for 3D WSNs in terms of coverage and connectivity.     

Critical mass and willingness to pay for social networks

Disagreement surrounds a formal definition of ‘critical mass’ and of the economic willingness to pay for membership in a social network. Our paper adapts work from percolation theory to analyze the structure of social networks, and draws an analogy for critical mass in social networks to the concept of phase changes in materials. We show how network growth can be actively managed, and define how to manage the willingness to pay for membership. We show, if achieving a critical mass of members in a social network is our objective, that prior to achieving critical mass, (1) the probability of accepting an invitation must vary inversely with individuals’ breadth of contacts; and (2) the number of special interest groups of any size will decrease following a power law until immediately below critical mass. Targeted invitations enabled through sophisticated programs such as AdWords and IndexTools can help to actively maximize the probability of forming an acquaintance link. Our model defines a willingness to pay for network membership that is nearly zero below critical mass, and is an involved function above critical mass whose shape appears to be close to a logarithmic function. Our robust measure of the connectedness of members of a particular social network yields values that are consistent with the independently developed metrics of Odlyzko and Tilly [Odlyzko, A., and Tilly, B. A refutation of Metcalfe’s Law and a better estimate for the value of networks and network interconnections, 2005 (downloaded from http://www.dtc.umn.edu/~odlyzko July 3, 2008)], and differ from eponymous ‘laws’ of Sarnoff, Metcalfe and Reed. There also appears to be plausible evidence in support of the market actually pricing networks at values close to Odlyzko and Tilly’s estimates.     

Accurate and robust estimation of phase error and its uncertainty of 50 GHz bandwidth sampling circuit

This paper discusses the dependence of the phase error on the 50 GHz bandwidth oscilloscope's sampling circuitry. We give the definition of the phase error as the difference between the impulse responses of the NTN (nose-to-nose) estimate and the true response of the sampling circuit. We develop a method to predict the NTN phase response arising from the internal sampling circuitry of the oscilloscope. For the default sampling-circuit configuration that we examine, our phase error is approximately 7.03° at 50 GHz. We study the sensitivity of the oscilloscope's phase response to parametric changes in sampling-circuit component values. We develop procedures to quantify the sensitivity of the phase error to each component and to a combination of components that depend on the fractional uncertainty in each of the model parameters as the same value, ±10%. We predict the upper and lower bounds of phase error, that is, we vary all of the circuit parameters simultaneously in such a way as to increase the phase error, and then vary all of the circuit parameters to decrease the phase error. Based on Type B evaluation, this method qualifies the impresses of all parameters of the sampling circuit and gives the value of standard uncertainty, 1.34°. This result is developed at the first time and has important practical uses. It can be used for phase calibration in the 50 GHz bandwidth large signal network analyzers (LSNAs).     

基于佳点集的蝙蝠定位算法在WSN中应用

针对无线传感器网络(WSN)节点的定位误差较大的的问题,提出一种新的基于佳点集的蝙蝠定位算法.在改进的算法中,采用基于佳点集的方法对蝙蝠种群个体进行初始化优化,有效提高种群多样性,避免算法过早陷入局部最优;引入部落机制及自适应更新方式,可有效避免局部最优解的吸引,加快收敛速度;通过重构部落利用pareto分级有效避免个别优秀个体被淘汰,增强了泛化能力,提高算法精度.通过MATLAB模拟仿真平台仿真实验表明,改进后的算法具有较好的收敛性和良好的寻优性能,降低测距误差对定位的影响,提高节点的定位精度.算法系统实现条件简单、精度高,具有较高的实际应用价值.     

移动通信网络的中性集故障诊断方法研究

随着故障诊断技术从面向网络设备逐渐向面向用户、面向业务的转变,故障识别能力和故障处理能力的不断提高,快速、准确地检测重大故障并及时收集重大故障信息,对缩短故障时长、提高工作效率、提升网络服务水平都具有重大意义。基于中性集故障诊断方法,本文提出一种故障特征权重和阶段数据权重的计算方法,并将此方法应用于移动通信网络的话音业务的故障诊断过程中。根据收集到的数据的统计分析结果,判断移动通信网络中未知故障样本的故障类型。通过举例分析,验证了本文所提出的故障特征权重和阶段数据权重设计方法的优越性。     

Scalable percolation search on complex networks

We introduce a scalable searching protocol for locating and retrieving content in random networks with heavy-tailed and in particular power-law (PL) degree distributions. The proposed algorithm is capable of finding any content in the network with probability one   in time O(logN)$\mathrm{O}(\log N)$, with a total traffic that provably scales sub-linearly with the network size, N. Unlike other proposed solutions, there is no need to assume that the network has multiple copies of contents; the protocol finds all contents reliably, even if every node in the network starts with a unique content. The scaling behavior of the size of the giant connected component of a random graph with heavy-tailed degree distributions under bond percolation is at the heart of our results. The percolation search algorithm can be directly applied to make unstructured peer-to-peer (P2P) networks, such as Gnutella, Limewire and other file-sharing systems (which naturally display heavy-tailed degree distributions and approximate scale-free network structures), scalable. For example, simulations of the protocol on the limewire crawl number 5 network [Ripeanu et al., Mapping the Gnutella network: properties of large-scale peer-to-peer systems and implications for system design, IEEE Internet Comput. J. 6 (1) (2002)], consisting of over 65,000 links and 10,000 nodes, shows that even for this snapshot network, the traffic can be reduced by a factor of at least 100, and yet achieve a hit-rate greater than 90%.     

基于计数排序的最小种子集贪心算法

网络最小种子集问题与网络影响最大化问题相关,研究的是对于具有节点阈值的网络,构造网络的最小节点子集,使得如果这个子集中的节点是活的,则在给定的影响传播模型下整个网络都受到影响。为此提出了新的贪心算法,以节点的度与阈值的差为关键值对网络节点进行计数排序,然后取值最小的节点进行处理。新算法在时间复杂度上改进了基于最小堆的种子点选取算法。在简单多数阈值模型上针对经典的无标度网络得到了所构造的种子集规模上界。实验在随机生成网络和一些实际网络数据集上进行,结果表明所提方法的有效性,特别在无标度网络上生成的种子集具有比相关算法更小的规模。