检索结果-内蒙古大学图书馆

FirmTruss Community Search in Multilayer Networks

PROCEEDINGS OF THE VLDB ENDOWMENT 2022年第3期16卷 505-518页

作者： Behrouz, Ali Hashemi, Farnoosh Lakshmanan, Laks V. S. Univ British Columbia Vancouver BC Canada

In applications such as biological, social, and transportation networks, interactions between objects span multiple aspects. For accurately modeling such applications, multilayer networks have been proposed. Community search allows for personalized community discovery and has a wide range of applications in large real-world networks. While community search has been widely explored for single-layer graphs, the problem for multilayer graphs has just recently attracted attention. Existing community models in multilayer graphs have several limitations, including disconnectivity, free-rider effect, resolution limits, and inefficiency. To address these limitations, we study the problem of community search over large multilayer graphs. We first introduce FirmTruss, a novel dense structure in multilayer networks, which extends the notion of truss to multilayer graphs. We show that FirmTrusses possess nice structural and computational properties and bring many advantages compared to the existing models. Building on this, we present a new community model based on FirmTruss, called FTCS, and show that finding an FTCS community is NP-hard. We propose two efficient 2-approximation algorithms, and show that no polynomial-time algorithm can have a better approximation guarantee unless P = NP. We propose an index-based method to further improve the efficiency of the algorithms. We then consider attributed multilayer networks and propose a new community model based on network homophily. We show that community search in attributed multilayer graphs is NP-hard and present an effective and efficient approximation algorithm. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Sampling-based dimension reduction for subspace approximation with outliers

引用

THEORETICAL COMPUTER SCIENCE 2021年 858卷 100-113页

作者： Deshpande, Amit Pratap, Rameshwar Microsoft Res India Bangalore Karnataka India IIT Mandi Suran India

The subspace approximation problem with outliers, for given n points in d dimensions x(1), x(2), ... , x(n) is an element of R-d, an integer 1 < k < d, and an outlier parameter 0 < alpha < 1, is to find a k-dimensional linear subspace of Rd that minimizes the sum of squared distances to its nearest (1 - alpha)n points. More generally, the Bp subspace approximation problem with outliers minimizes the sum of p-th powers of distances instead of the sum of squared distances. Even the case of p = 2 or robust PCA is non-trivial, and previous work requires additional assumptions on the input or generative models for it. Any multiplicative approximation algorithm for the subspace approximation problem with outliers must solve the robust subspace recovery problem, a special case in which the (1 - alpha)n inliers in the optimal solution are promised to lie exactly on a k-dimensional linear subspace. However, robust subspace recovery is Small Set Expansion (SSE)-hard, and known algorithmic results for robust subspace recovery require strong assumptions on the input, e.g., any d outliers must be linearly independent. In this paper, we show how to extend dimension reduction techniques and bi-criteria approximations based on sampling and coresets to the problem of subspace approximation with outliers. To get around the SSE-hardness of robust subspace recovery, we assume that the squared distance error of the optimal k-dimensional subspace summed over the optimal (1 - alpha)n inliers is at least delta times its squared-error summed over all n points, for some 0 < delta <= 1 - alpha. Under this assumption, we give an efficient algorithm to find a weak coreset or a subset of poly(k/is an element of) log(1/delta) log log(1/delta) points whose span contains a k-dimensional subspace that gives a multiplicative (1 + epsilon-approximation to the optimal solution. Our technique is based on the squared-length sampling algorithm suggested for low-rank approximation problems in the seminal w

关键词： Low-rank approximation Dimensionality reduction Outliers approximation algorithms Sampling

来源：评论

学校读者我要写书评

暂无评论

Influence Spread in Location-Based Social Network: An Efficient Algorithm of Epidemic Controlling

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2022年第4期9卷 1132-1143页

作者： Yao, Xiaopeng Han, Xiaowei Gu, Yue Gu, Chonglin Huang, Hejiao Harbin Inst Technol Sch Comp Sci & Technol Shenzhen 518055 Peoples R China

Much work has already been studied on the interrelation between the epidemic spreading and awareness spreading to prevent infections in a social network. By selecting seed users to spread awareness, we can control epidemic spreading. However, selecting seed users with the maximum influential users may not be the best solution in location-based social networks. Therefore, it is challenging to determine users to spread the information (the awareness of prevention) in these networks. The minimized epidemic infection (MEI) problem aims to find a seed set with k seed users such that the infection users can be minimized. In this article, we propose a piecewise function to measure the probability of each user being infected, which considers the distance and time. Then, we propose an algorithm called location-infected-greedy (LIG) to solve the MEI problem by finding the seed nodes that consider the probability of infection, time of check-in, location information, and influence of users. In the meantime, LIG can obtain an upper bound of the data-dependent approximate ratio, and it runs in O(kn(2)), where n is the total number of nodes and k is the number of seed nodes. Finally, extensive contrast experiments on real-world location-based social networks show that our algorithm is efficient and effective.

关键词： Social networking (online) Epidemics Predictive models approximation algorithms Probability Prediction algorithms Mathematical models approximation algorithm epidemic infected location-based social network

来源：评论

学校读者我要写书评

暂无评论

Hiding in Temporal Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第3期9卷 1645-1657页

作者： Waniek, Marcin Holme, Petter Rahwan, Talal New York Univ Abu Dhabi Abu Dhabi 129188 U Arab Emirates Tokyo Inst Technol Inst Innovat Res Tokyo 1528550 Japan

Social network analysis tools can infer various attributes just by scrutinizing one's connections. Several researchers have studied the problem faced by an evader whose goal is to strategically rewire their social connections in order to mislead such tools, thereby concealing their private attributes. However, to date this literature has only considered static networks, while neglecting the more general case of temporal networks, where the structure evolves over time. Driven by this observation, we study how the evader can conceal their importance from an adversary armed with temporal centrality measures. We consider computational and structural aspects of this problem: Is it computationally feasible to calculate optimal ways of hiding? If it is, what network characteristics facilitate hiding? This topic has been studied in static networks, but in this work, we add realism to the problem by considering temporal networks of edges changing in time. We find that it is usually computationally infeasible to find the optimal way of hiding. On the other hand, by manipulating one's contacts, one could add a surprising amount of privacy. Compared to static networks, temporal networks offer more strategies for this type of manipulation and are thus, to some extent, easier to hide in.

关键词： Social networking (online) Privacy Time measurement Licenses approximation algorithms Optimization Network analyzers Computational complexity social media misinformation network centrality network theory

来源：评论

学校读者我要写书评

暂无评论

Model-Based Deep Learning for Joint Activity Detection and Channel Estimation in Massive and Sporadic Connectivity

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2022年第11期21卷 9806-9817页

作者： Johnston, Jeremy Wang, Xiaodong Columbia Univ Dept Elect Engn New York NY 10027 USA

We present two model-based neural network architectures purposed for sporadic user detection and channel estimation in massive machine-type communications. In the scenario under consideration, a base station assigns the users a set of pilot sequences that is linearly dependent, but because user activity is sporadic the detection/estimation problem is amenable to sparse recovery algorithms. Further, we consider a millimeter-wave wireless channel, so that the channel vectors are sparse in a known dictionary. We apply the deep unfolding framework to design custom neural network layers by unrolling two iterative optimization algorithms: (1) linearized alternating direction method of multipliers, which we apply to a constrained convex problem, and (2) vector approximate message passing featuring a novel denoiser based on the iterative shrinkage thresholding algorithm. The networks thus inherit domain knowledge as encapsulated by the signal model, and suitable operations as informed by the algorithms-in the same spirit as convolutional networks that exploit structure inherent in images and audio, except grounded in optimization and statistics. The networks, trained on synthetic data generated from the block-fading millimeter-wave multiple access channel model, offer improved complexity and accuracy relative to their iterative counterparts, and are potentially a boon to cell-free MIMO systems.

关键词： Channel estimation Neural networks Iterative algorithms Time measurement approximation algorithms Wireless communication NOMA Deep learning deep unfolding neural network massive machine-type communication massive connectivity multiple measurement vector joint activity detection and channel estimation ADMM VAMP ISTA

来源：评论

学校读者我要写书评

暂无评论

Minimum budget for misinformation detection in online social networks with provable guarantees

引用

OPTIMIZATION LETTERS 2022年第2期16卷 515-544页

作者： Pham, Canh V. Pham, Dung V. Bui, Bao Q. Nguyen, Anh V. Phenikaa Univ ORLab Fac Comp Sci Hanoi 12116 Vietnam Peoples Secur Acad Fac Informat Technol & Secur Hanoi Vietnam Vietnam Acad Sci & Technol Inst Informat Technol Hanoi Vietnam

Misinformation detection in Online Social Networks has recently become a critical topic due to its important role in restraining misinformation. Recent studies have showed that machine learning methods can be used to detect misinformation/fake news/rumors by detecting user's behaviour. However, we can not implement this strategy for all users on a social network due to the limitation of budget. Therefore, it is critical to optimize the monitor/sensor placement to effectively detect misinformation. In this paper, we investigate Minimum Budget for Misinformation Detection problem which aims to find the smallest set of nodes to place monitors in a social network so that detection function is at least a given threshold. Beside showing the inapproximability of the problem under the well-known Independent Cascade diffusion model, we then propose three approximation algorithms including: Greedy, Sampling-based Misinformation Detection and Importance Sampling-based Misinformation Detection. Greedy is a deterministic approximation algorithm which utilizes the properties of monotone and submodular of the detection function. The rest is two randomized algorithms with provable guarantees based on developing two novel techniques (1) estimating detection function by using the concepts of influence sample and importance influence sample with proof of correctness, and (2) an algorithmic framework to select the solution with theoretical analysis. Experiments on real social networks show the effectiveness and scalability of our algorithms.

关键词： Online social network Misinformation detection approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Influence Maximization Through Scheduled Seeding in a Real-World Setting

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2022年第2期9卷 494-507页

作者： Lev, Tomer Ben-Gal, Irad Shmueli, Erez Tel Aviv Univ Dept Ind Engn IL-69978 Tel Aviv Israel

In this article, we evaluate, for the first time, the potential of a scheduled seeding strategy for influence maximization in a real-world setting. We first propose methods for analyzing historical data to quantify the infection probability of a node with a given set of properties in a given time and assess the potential of a given seeding strategy to infect nodes. Then, we examine the potential of a scheduled seeding strategy by analyzing a real-world large-scale dataset containing both the network topology as well as the nodes' infection times. Specifically, we use the proposed methods to demonstrate the existence of two important effects in our dataset: a complex contagion effect and a diminishing social influence effect. As shown in a recent study, the scheduled seeding approach is expected to benefit greatly from the existence of these two effects. Finally, we compare a number of benchmark seeding strategies to a scheduled seeding strategy that ranks nodes based on a combination of the number of infectious friends (NIF) they have, as well as the time that has passed since they became infectious. Results of our analyses show that for a seeding budget of 1%, the scheduled seeding strategy yields a convergence rate that is 14% better than a seeding strategy based solely on their degrees, and 215% better than a random seeding strategy, which is often used in practice.

关键词： Social networking (online) Mathematical model Statistics Sociology Analytical models approximation algorithms Greedy algorithms Influence maximization scheduled seeding social network analysis

来源：评论

学校读者我要写书评

暂无评论

Failure-Tolerant Monitoring Based on Spatial-Temporal Correlation via Mobile Sensors for Large-Scale Acyclic Flow Systems in Smart Cities

引用

IEEE INTERNET OF THINGS JOURNAL 2022年第20期9卷 19561-19574页

作者： Zhang, Haihan Liang, Junbin Leung, Victor C. M. Guangxi Univ Sch Comp Elect & Informat Guangxi Key Lab Multimedia Commun & Network Techn Nanning 530005 Peoples R China Shenzhen Univ Coll Comp Sci & Software Engn Shenzhen 518060 Peoples R China Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

Large-scale acyclic flow systems (LSAFSs) are models of pipeline networks that are used to transport important resources, such as water, oil, and natural gas in smart cities. LSAFSs have features of complex topology and deep-underground deployment, which would cause accidents, such as leakages and pollution that are difficult to be detected in time. Mobile sensors (MSs)-based monitoring schemes appear as an effective solution in recent years to handle this situation. These schemes drop MSs into an LSAFS from specified locations, and the MSs will move along with fluid inside the LSAFS to collect data. When the MSs pass through a predeployed and activated receiver node (RN), they will upload their data to the RN. However, how to decide the optimal locations and timings for dropping of the MSs and the best activation periods and deployment locations of the RNs, such that total length of monitored pipelines in the LSAFS is maximized, as well as energy consumption of the RNs is minimized, is a challenging problem. The problem is more challenging if potential uploading failures and undetermined movement of the MSs are considered. In this article, we first formalize the problem as a multiobjective optimization problem. Then, we decompose the problem into a submodular optimization problem and an union set optimization problem, and prove they are NP-hard. Next, an approximate algorithm based on the Pigeonhole principle is proposed to solve the first problem, and a heuristic algorithm based on the inclusion-exclusion principle is proposed to solve the second problem. Extensive theoretical analyses and simulations show that the proposed algorithms outperform state-of-the-art algorithms.

关键词： Monitoring Pipelines Sensors Optimization Energy consumption approximation algorithms Costs Mobile sensor (MS) networks node deployment pipeline networks submodular functions

来源：评论

学校读者我要写书评

暂无评论

The Power of Subsampling in Submodular Maximization

引用

MATHEMATICS OF OPERATIONS RESEARCH 2022年第2期47卷 1365-1393页

作者： Harshaw, Christopher Kazemi, Ehsan Feldman, Moran Karbasi, Amin Yale Univ Dept Comp Sci New Haven CT 06520 USA Google CH-8002 Zurich Switzerland Univ Haifa Dept Comp Sci IL-3498838 Haifa Israel Yale Univ Dept Elect Engn New Haven CT 06520 USA Yale Univ Dept Stat & Data Sci New Haven CT 06520 USA

We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SAMPLEGREEDY, which obtains a (p + 2 + o(1))-approximation for maximizing a submodular function subject to a p-extendible system using O(n + nk/p) evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p + 1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present Sample-Streaming, which obtains a (4p + 2 - o(1))-approximation for maximizing a submodular function subject to a p-matchoid using O(k) memory and O(km/p) evaluation and feasibility queries per element, and m is the number of matroids defining the p-matchoid. The approximation ratio improves to 4p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.

关键词： submodular maximization subsampling streaming algorithms approximation algorithms p-extendible systems p-matchoids

来源：评论

学校读者我要写书评

暂无评论

feGRASS: Fast and Effective Graph Spectral Sparsification for Scalable Power Grid Analysis

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2022年第3期41卷 681-694页

作者： Liu, Zhiqiang Yu, Wenjian Feng, Zhuo Tsinghua Univ Dept Comp Sci & Technol BNRist Beijing 100084 Peoples R China Stevens Inst Technol Dept Elect & Comp Engn Hoboken NJ 07030 USA

Graph spectral sparsification aims to find a ultrasparse subgraph which can preserve the spectral properties of the original graph. The subgraph can be leveraged to construct a preconditioner to speed up the solution of the original graph's Laplacian matrix. In this work, we propose feGRASS, a fast and effective graph spectral sparsification approach for the problem of large-scale power grid analysis and other problems with similar graphs. The proposed approach is based on two novel concepts: 1) effective edge weight and 2) spectral edge similarity. The former takes advantage of node degrees and breadth-first-search (BFS) distances, which leads to a scalable algorithm for generating low-stretch spanning trees (LSSTs). Then, the latter concept is leveraged during the recovery of spectrally critical off-tree edges to produce spectrally similar subgraphs. Compared with the most recent competitor [1], the proposed approach is much faster for producing high-quality spectral sparsifiers. Extensive experimental results have been demonstrated to illustrate the superior efficiency of a preconditioned conjugate gradient (PCG) algorithm based on the proposed approach, for solving large power grid problems and many other real-world graph Laplacians. For instance, a power grid matrix with 60 million unknowns and 260 million nonzeros can be solved (at a 1E-3 accuracy level) within 196 s and 12 PCG iterations, on a single CPU core.

关键词： Power grids Laplace equations Symmetric matrices Eigenvalues and eigenfunctions approximation algorithms Resistance Task analysis Iterative solver low-stretch spanning tree (LSST) power grid analysis spectral graph sparsification

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：