Influence maximization with limit cost in social network

Social networking service (SNS) applications are changing the way information spreads in online communities. As real social relationships are projected into SNS applications, word of mouth has been an important factor in the information spreading processes of those applications. By assuming each user needs a cost to accept some specific information, this paper studies the initial "seed user" selection strategy to maximize information spreading in a social network with a cost budget. The main contributions of this paper are: 1) proposing a graphic SEIR model (gSEIR) by extending the epidemic compartmental model to simulate the dynamic information spreading process between individuals in the social network; 2) proposing a formal definition for the influence maximization problem with limit cost (IMLC) in social networks, and proving that this problem can be transformed to the weighted set-cover problem (WSCP) and thus is NP-Complete; 3) providing four different greedy algorithms to solve the IMLC problem; 4) proposing a heuristic algorithm based on the method of Lagrange multipliers (HILR) for the same problem; 5) providing two parts of experiments to test the proposed models and algorithms in this paper. In the first part, we verify that gSEIR can generate similar macro-behavior as an SIR model for the information spreading process in an online community by combining the micro-behaviors of all the users in that community, and that gSEIR can also simulate the dynamic change process of the statuses of all the individuals in the corresponding social networks during the information spreading process. In the second part, by applying the simulation result from gSEIR as the prediction of information spreading in the given social network, we test the effectiveness and efficiency of all provided algorithms to solve the influence maximization problem with cost limit. The result show that the heuristic algorithm HILR is the best for the IMLC problem.     

Efficient algorithms for influence maximization in social networks

In recent years, due to the surge in popularity of social-networking web sites, considerable interest has arisen regarding influence maximization in social networks. Given a social network structure, the problem of influence maximization is to determine a minimum set of nodes that could maximize the spread of influences. With a large-scale social network, the efficiency and practicability of such algorithms are critical. Although many recent studies have focused on the problem of influence maximization, these works in general are time-consuming when a social network is large-scale. In this paper, we propose two novel algorithms, CDH-Kcut and Community and Degree Heuristic on Kcut/SHRINK, to solve the influence maximization problem based on a realistic model. The algorithms utilize the community structure, which significantly decreases the number of candidates of influential nodes, to avoid information overlap. The experimental results on both synthetic and real datasets indicate that our algorithms not only significantly outperform the state-of-the-art algorithms in efficiency but also possess graceful scalability.     

Multi-stage opinion maximization in social networks

Neural Computing and Applications - Opinion maximization is a crucial optimization approach, which can be used in preventative health, such as heart disease, stroke or diabetes. The key issue of...     

A utility maximization approach for information-communication tradeoff in Wireless Body Area Networks

Healthcare systems have made a dramatic shift towards ubiquitous monitoring in the recent past. The reasons for such a change have been ease of timely diagnosis, convenience and comfort of clinical treatments. Wireless Body Area Networks (WBANs) are mainly characterized by deployment of biomedical sensors around human body which transmit vital signs measurements about the health status of the patient. Unfortunately, the huge traffic load of clinical data and limited resources of biomedical sensors make the efficiency of long-term operations almost impossible. Therefore, it is necessary to make significant advances in sensor’s energy saving. Our idea is to reduce the activities of some sensors depending on the relevance between the data they measure and the diseases to detect. This paper shows how to extend the lifetime of medical WBANs by appropriately taking benefit of correlation between the knowledge about the disease and sensing data to drive the best scheduling of the medical sensors. For that, the theoretical framework of an economic approach, i.e., network utility maximization, is developed for sensor scheduling under operations cost constraint. It is shown that the compact subset of sensors can be found to provide necessary information for timely and correct diagnoses. Based on the theoretical framework, an algorithm combining sensor selection and information gain is then proposed. Simulation results show that the algorithm achieves high performance in terms of energy saving vs latency in disease detection.     

社交网络中对立影响最大化算法

已有社交网络影响力传播的研究工作主要关注单源信息传播情形,较少考虑对立的传播形式。针对对立影响最大化问题,扩展热量传播模型为多源热量传播模型,并提出一种预选式贪心近似（PSGA）算法。为验证算法有效性,选取7种具有代表性的种子挖掘方法,以对立影响最大化传播收益、算法运行时间及种子的富集程度为评价指标,在不同种类社会网络数据集上开展实验。结果表明,PSGA算法所选的种子传播能力更强,且密集程度低、表现稳定,在传播初期占据优势,可以认为PSGA算法能够解决对立影响最大化问题。     

Team formation with influence maximization for influential event organization on social networks

Online event-based social services allow users to organize social events by specifying the themes, and invite friends to participate social events. While the event information can be spread over the social network, it is expected that by certain communication between event hosts, users interested in the event themes can be as more as possible. In this paper, by combining the ideas of team formation and influence maximization, we formulate a novel research problem, Influential Team Formation (ITF), to facilitate the organization of social events. Given a set L of required labels to describe the event topics, a social network, and the size k of the host team, ITF is to find a k-node set S that satisfying L and maximizing the Influence-Cost Ratio (i.e., the influence spread per communication cost between team members). Since ITF is proved to be NP-hard, we develop two greedy algorithms and one heuristic method to solve it. Extensive experiments conducted on Facebook and Google+ datasets exhibit the effectiveness and efficiency of the proposed methods. In addition, by employing the real event participation data in Meetup, we show that ITF with the proposed solutions is able to predict organizers of influential events.     

基于网络效用最大化与冲突避免的无线传感器网络MAC协议

针对周期汇报型无线传感器网络(WSN)中的无线信号冲突和能量利用效率问题,提出了一种基于网络效用最大化与冲突避免的媒体访问控制(UM-MAC)协议。该协议基于时分多路复用(TDMA)调度机制,将效用模型引入无冲突的节点工作时隙分配过程中,把链路可靠性、网络能耗归纳到一个统一的效用优化框架中;进而提出了一个启发式算法,使网络能够快速找到一个基于网络效用最大化与冲突避免的节点工作时隙调度方案。将UM-MAC协议与S-MAC协议和冲突避免MAC(CA-MAC)协议进行比较,在不同节点数量的网络环境中,UM-MAC获得的网络效用较大,平均数据包成功发送率较高,生命周期介于S-MAC与CA-MAC之间,在不同的网络负载下所有节点发数据包到汇聚节点的平均时延有所增加。仿真实验结果表明:UM-MAC协议较好地解决了冲突干扰问题,提高了网络的数据包成功发送率和能量利用效率等性能;在低网络负载时,TDMA类协议的性能并不比竞争类协议好。     

Content-aware rate allocation for efficient video streaming via dynamic network utility maximization

Nowadays it is vital to design robust mechanisms to provide QoS for multimedia applications as an integral part of the network traffic. The main goal of this paper is to provide an efficient rate control scheme to support content-aware video transmission mechanism with buffer underflow avoidance at the receiver in congested networks. Towards this, we introduce a content-aware time-varying utility function, in which the quality impact of video content is incorporated into its mathematical expression. Moreover, we analytically model the buffer requirements of video sources in two ways: first as constraints of the optimization problem to guarantee a minimum rate demand for each source, and second as a penalty function embedded as part of the objective function attempting to achieve the highest possible rate for each source. Then, using the proposed analytical model, we formulate a dynamic network utility maximization problem, which aims to maximize the aggregate hybrid objective function of sources subject to capacity and buffer constraints. Finally, using primal–dual method, we solve DNUM problem and propose a distributed algorithm called CA-DNUM that optimally allocates the shared bandwidth to video streams. The experimental results demonstrate the efficacy and performance improvement of the proposed content-aware rate allocation algorithm for video sources in different scenarios.     

Scalable influence maximization for independent cascade model in large-scale social networks

Influence maximization, defined by Kempe et al. (SIGKDD 2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of Kempe et al. (SIGKDD 2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this article, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread—it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100–260% increase in influence spread.     

基于k-核过滤的社交网络影响最大化算法

针对现有社交网络影响最大化算法影响范围小和时间复杂度高的问题,提出一种基于独立级联模型的k-核过滤算法。首先,介绍了一种节点影响力排名不依赖于整个网络的现有影响力最大化算法;然后,通过预训练k,找到对现有算法具有最佳优化效果且与选择种子数无关的k值;最后,通过计算图的k-核过滤不属于k-核子图的节点和边,在k-核子图上执行现有影响最大化算法,达到降低计算复杂度的目的。为验证k-核过滤算法对不同算法有不同的优化效果,在不同规模数据集上进行了实验。结果显示,应用k-核过滤算法后：与原PMIA算法相比,影响范围最多扩大13.89%,执行时间最多缩短8.34%;与原核覆盖算法（CCA）相比,影响范围没有太大差异,但执行时间最多缩短28.5%;与OutDegree算法相比,影响范围最多扩大21.81%,执行时间最多缩短26.96%;与Random算法相比,影响范围最多扩大71.99%,执行时间最多缩短24.21%。进一步提出了一种新的影响最大化算法GIMS,它比PMIA和IRIE的影响范围更大,执行时间保持在秒级别,而且GIMS算法的k-核过滤算法与原GIMS算法的影响范围和执行时间差异不大。实验结果表明,k-核过滤算法能够增大现有算法选择种子节点集合的影响范围,并且减少执行时间;GIMS算法具有更好的影响范围效果和执行效率,并且更加鲁棒。     

Three-hop velocity attenuation propagation model for influence maximization in social networks

World Wide Web - In the study of influence maximization in social networks, the speed of information dissemination decreases with increasing time and distance. The investigation of the...     

Identifying valuable customers on social networking sites for profit maximization

With the tremendous popularity of social networking sites (SNS) in this era of Web 2.0, enterprises have begun to explore the feasibility of using SNS as platforms to conduct targeted marking and reputation management. Given huge number of users on SNS, how to choose appropriate users as the targets is the key for enterprises to conduct cost-effective targeted marketing and reputation management on SNS. This paper introduces a novel model for effectively identifying the most valuable users from SNS. Furthermore, we propose to use an optimization technique named semidefinite programming (SDP) to identify the most valuable customers that can generate the maximum of total profit. Our empirical evaluation on a real data set extracted from a popular SNS shows that the proposed model achieves much higher profits than benchmark methods. This study opens doors to more effective targeted marketing and reputation management on SNS.     

High utility K-anonymization for social network publishing

Privacy and utility are two main desiderata of good sensitive information publishing schemes. For publishing social networks, many existing algorithms rely on \(k\) -anonymity as a criterion to guarantee privacy protection. They reduce the utility loss by first using the degree sequence to model the structural properties of the original social network and then minimizing the changes on the degree sequence caused by the anonymization process. However, the degree sequence-based graph model is simple, and it fails to capture many important graph topological properties. Consequently, the existing anonymization algorithms that rely on this simple graph model to measure utility cannot guarantee generating anonymized social networks of high utility. In this paper, we propose novel utility measurements that are based on more complex community-based graph models. We also design a general \(k\) -anonymization framework, which can be used with various utility measurements to achieve \(k\) -anonymity with small utility loss on given social networks. Finally, we conduct extensive experimental evaluation on real datasets to evaluate the effectiveness of the new utility measurements proposed. The results demonstrate that our scheme achieves significant improvement on the utility of the anonymized social networks compared with the existing anonymization algorithms. The utility losses of many social network statistics of the anonymized social networks generated by our scheme are under 1 % in most cases.     

Anonymizing popularity in online social networks with full utility

With the rapid growth of social network applications, more and more people are participating in social networks. Privacy protection in online social networks becomes an important issue. The illegal disclosure or improper use of users’ private information will lead to unaccepted or unexpected consequences in people’s lives. In this paper, we concern on authentic popularity disclosure in online social networks. To protect users’ privacy, the social networks need to be anonymized. However, existing anonymization algorithms on social networks may lead to nontrivial utility loss. The reason is that the anonymization process has changed the social network’s structure. The social network’s utility, such as retrieving data files, reading data files, and sharing data files among different users, has decreased. Therefore, it is a challenge to develop an effective anonymization algorithm to protect the privacy of user’s authentic popularity in online social networks without decreasing their utility. In this paper, we first design a hierarchical authorization and capability delegation (HACD) model. Based on this model, we propose a novel utility-based popularity anonymization (UPA) scheme, which integrates proxy re-encryption with keyword search techniques, to tackle this issue. We demonstrate that the proposed scheme can not only protect the users’ authentic popularity privacy, but also keep the full utility of the social network. Extensive experiments on large real-world online social networks confirm the efficacy and efficiency of our scheme.     

基于网络效用最大化的车联网功率控制算法

针对车联网（IoV）中车流密度增加到一定程度时,即使无线信道中只有信标消息,信道拥塞也会发生的问题,提出一种分布式加权公平功率控制（D-WFPC）算法。首先,考虑车联网的实际信道特性,采用Nakagami-m衰落信道模型建立随机信道模型;然后,考虑车联网中节点的移动性,基于网络效用最大化（NUM）模型建立功率控制优化问题,控制本地信道负载在阈值之下,从而避免拥塞;最后,通过对偶分解和迭代法解决该问题,设计分布式算法,每辆车根据周围环境的邻居车辆的信标消息,动态调整发射功率。仿真实验中,与固定发射功率方案相比,随着车流密度增大,D-WFPC算法能有效降低时延和丢包率,最高降幅分别达到24%和44%;与公平分布式发射功率拥塞控制（FCCP）算法相比,D-WFPC算法全程性能占优,时延和丢包率的最高降幅分别达到10%和4%。仿真结果表明,D-WFPC算法能快速收敛,保证车联网中消息的低时延、高可靠传输。     

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

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

成本控制下的快速影响最大化算法

针对成本控制下影响最大化时间复杂度高的问题,提出一种快速的最大化算法BCIM。首先提出对初始节点进行多次传播的传播模型;其次选择高影响力节点作为备用种子,并基于近距离影响减少计算节点影响范围的工作量;最后利用动态规划方法在每组备用种子中最多选择一个种子。仿真实验表明,与随机算法Random、每轮取影响力增量最大的节点的贪心算法Greedy_MII、每轮取影响力增量与成本比值最大的节点的贪心算法Greedy_MICR相比,在影响范围上,BICM接近或优于Greedy_MICR及Greedy_MII,远次于Random;在种子集合的质量上,BCIM、Greedy_MICR、Greedy_MII三者差距较小,但都远远好于Random;在运行时间上,BCIM是Random的几倍,而两个贪心算法都是BCIM的几百倍。BCIM算法能在较短时间内找到更有效的种子集合。