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

Maximizing the Spread of Effective Information in Social Networks

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第4期35卷 4062-4076页

作者： Zhang, Haonan Fu, Luoyi Ding, Jiaxin Tang, Feilong Xiao, Yao Wang, Xinbing Chen, Guihai Zhou, Chenghu Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Comp Sci & Engn Shanghai 200240 Peoples R China Chinese Acad Sci Inst Geog Sci & Nat Resources Res Beijing 100045 Peoples R China

Influence maximization through social networks has aroused tremendous interests nowadays. However, people's various expressions or feelings about a same idea often cause ambiguity via word of mouth. Consequently, the problem of how to maximize the spread of "effective information" still remains largely open. In this paper, we consider a practical setting where ideas can deviate from their original version to invalid forms during message passing, and make the first attempt to seek a union of users that maximizes the spread of effective influence, which is formulated as an Influence Maximization with Information Variation (IMIV) problem. To this end, we model the information as a vector, and quantify the difference of two arbitrary vectors as a distance by a matching function. We further establish a process where such distance increases with the propagation and ensure the recipient whose vector distance is less than a threshold can be effectively influenced. Due to the NP-hardness of IMIV, we greedily select users that can approximately maximize the estimation of effective propagation. Especially, for networks of small scales, we derive a condition under which all the users can be effectively influenced. Our models and theoretical findings are further consolidated through extensive experiments on real-world datasets.

关键词： Social networking (online) Mouth Smart phones Estimation Approximation algorithms Time complexity Statistics Social network influence maximization information variation greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

On a partition LP relaxation for min-cost 2-node connected spanning subgraphs

引用

OPERATIONS RESEARCH LETTERS 2023年第3期51卷 289-295页

作者： Grout, Logan Cheriyan, Joseph Laekhanukit, Bundit Cornell Univ Operat Res & Informat Engn 206 Rhodes Hall Ithaca NY 14853 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada Shanghai Univ Finance & Econ Inst Theoret Comp Sci Shanghai Peoples R China

Our motivation is to improve on the best approximation guarantee known for the problem of finding a minimum-cost 2-node connected spanning subgraph of a given undirected graph with nonnegative edge costs. We present an LP (Linear Programming) relaxation based on partition constraints. The special case where the input contains a spanning tree of zero cost is called 2NC-TAP. We present a greedy algorithm for 2NC-TAP, and we analyze it via dual-fitting for our partition LP relaxation. (c) 2023 Elsevier B.V. All rights reserved.

关键词： 2-node connected graphs Approximation algorithms Connectivity augmentation greedy algorithm Network design Partition relaxation

来源：评论

学校读者我要写书评

暂无评论

Parallel Heuristic Methods to Accelerate Best Equivocation Code Generation

引用

IEEE ACCESS 2023年 11卷 44136-44149页

作者： Li, Yanchen Zhang, Ke Ino, Fumihiko Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan Wuhan Univ Technol Sch Informat Engn Wuhan 430070 Hubei Peoples R China

In this paper, we propose parallel heuristic methods to accelerate the generation of (n, m) best equivocation code (BEC), where n and m are code and message lengths, respectively. The proposed dynamic programming (DP) method and greedy method extend a previous heuristics method by reducing the time complexity of the code generation process. The DP method produces the same codes as the previous method but incurs an overhead for data reuse. In contrast, the greedy method avoids this overhead but generates slightly different codes due to its heuristic approach. We parallelize the proposed methods by exploiting coarse-grained and fine-grained parallelisms, which achieve further acceleration on multicore CPU and graphics processing unit (GPU) systems, respectively. Experimental results demonstrate that the proposed DP and greedy methods reduce the sequential generation time to a quarter, as indicated by theoretical complexity analysis. In addition, the parallel implementation achieves linear speedup on a multicore CPU system, and the GPU implementation realizes coalesced memory accesses, resulting in 17x acceleration over the eight-core CPU implementation. We found that the greedy method produced different codes that differ from the previous and DP methods;however, the generated codes had higher equivocation rates than those generated by a naive random method. We believe that the proposed parallel methods can effectively accelerate BEC generation for large m and n values, especially with larger values of n relative to m.

关键词： Dynamic programming GPU greedy algorithm multicore CPU parallel processing syndrome coding

来源：评论

学校读者我要写书评

暂无评论

Hierarchical User-Driven Trajectory Planning and Charging Scheduling of Autonomous Electric Vehicles

引用

IEEE TRANSACTIONS ON TRANSPORTATION ELECTRIFICATION 2023年第1期9卷 1736-1749页

作者： Saatloo, Amin Mansour Mehrabi, Abbas Marzband, Mousa Aslam, Nauman Northumbria Univ Fac Engn & Environm Dept Comp & Informat Sci Newcastle Upon Tyne NE1 8ST Tyne & Wear England Northumbria Univ Fac Engn & Environm Newcastle Upon Tyne NE1 8ST Tyne & Wear England King Abdulaziz Univ Ctr Res Excellence Renewable Energy & Power Syst Jeddah 21589 Saudi Arabia

Autonomous electric vehicles (A-EVs), regarded as one of the innovations to accelerate transportation electrification, have sparked a flurry of interest in trajectory planning and charging scheduling. In this regard, this work employs mobile edge computing (MEC) to design a decentralized hierarchical algorithm for finding an optimal path to the nearby A-EV parking lots (PLs), selecting the best PL, and executing an optimal charging scheduling. The proposed model makes use of unmanned aerial vehicles (UAVs) to assist edge servers in trajectory planning by surveying road traffic flow in real time. Furthermore, the target PLs are selected using a user-driven multiobjective problem to minimize the cost and waiting time of A-EVs. To tackle the complexity of the optimization problem, a greedy-based algorithm has been developed. Finally, charging/discharging power is scheduled using a local optimizer based on the PLs' real-time loads, which minimizes the deviation of the charging/discharging power from the average load. The obtained results show that the proposed model can handle charging/discharging requests of on-move A-EVs and bring fiscal and nonfiscal benefits for A-EVs and the power grid, respectively. Moreover, it observed that user satisfaction in terms of traveling time and traveling distance is increased by using the edge-UAV model.

关键词： Costs Real-time systems Optimization Trajectory planning Processor scheduling Vehicle-to-grid Roads Autonomous electric vehicle (A-EV) greedy algorithm mobile edge computing (MEC) trajectory planning vehicle-to-grid (V2G)

来源：评论

学校读者我要写书评

暂无评论

Summarizing User-item Matrix By Group Utility Maximization

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2023年第6期17卷 1-22页

作者： Wang, Yongjie Wang, Ke Long, Cheng Miao, Chunyan Nanyang Technol Univ N4-B3-0650 Nanyang Ave Singapore 639798 Singapore Simon Fraser Univ 8888 Univ Dr Burnaby BC V5A 1S6 Canada Nanyang Technol Univ N4-2c-117a50 Nanyang Ave Singapore 639798 Singapore

A user-item utility matrix represents the utility (or preference) associated with each (user, item) pair, such as citation counts, rating/vote on items or locations, and clicks on items. A high utility value indicates a strong association of the pair. In this work, we consider the problem of summarizing strong association for a large user-item matrix using a small summary size. Traditional techniques fail to distinguish user groups associated with different items (such as top-l item selection) or fail to focus on high utility (such as similaritybased subspace clustering and biclustering). We formulate a new problem, called Group Utility Maximization (GUM), to summarize the entire user population through k user groups and l items for each group;the goal is to maximize the total utility of selected items over all groups collectively. We show this problem is NPhard even for l = 1. We present two algorithms. One greedily finds the next group, called greedy algorithm, and the other iteratively refines existing k groups, called k-max algorithm. greedy algorithm provides the (1- 1/e) approximation guarantee for a nonnegative utility matrix, whereas k-max algorithm is more efficient for large datasets. We evaluate these algorithms on real-life datasets.

关键词： Data summarization greedy algorithm k-max algorithm group utility maximization

来源：评论

学校读者我要写书评

暂无评论

Large-Scale Bayesian Optimal Experimental Design with Derivative-Informed Projected Neural Network

引用

JOURNAL OF SCIENTIFIC COMPUTING 2023年第1期95卷 1-20页

作者： Wu, Keyi O'Leary-Roseberry, Thomas Chen, Peng Ghattas, Omar Univ Texas Austin Dept Math 2515 Speedway Austin TX 78712 USA Univ Texas Austin Oden Inst Computat Engn & Sci 201 E 24th St Austin TX 78712 USA Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA 30308 USA Univ Texas Austin Dept Geol Sci & Mech Engn Austin TX 78712 USA

We address the solution of large-scale Bayesian optimal experimental design (OED) problems governed by partial differential equations (PDEs) with infinite-dimensional parameter fields. The OED problem seeks to find sensor locations that maximize the expected information gain (EIG) in the solution of the underlying Bayesian inverse problem. Computation of the EIG is usually prohibitive for PDE-based OED problems. To make the evaluation of the EIG tractable, we approximate the (PDE-based) parameter-to-observable map with a derivative-informed projected neural network (DIPNet) surrogate, which exploits the geometry, smoothness, and intrinsic low-dimensionality of the map using a small and dimension-independent number of PDE solves. The surrogate is then deployed within a greedy algorithm-based solution of the OED problem such that no further PDE solves are required. We analyze the EIG approximation error in terms of the generalization error of the DIPNet and show they are of the same order. Finally, the efficiency and accuracy of the method are demonstrated via numerical experiments on OED problems governed by inverse scattering and inverse reactive transport with up to 16,641 uncertain parameters and 100 experimental design variables, where we observe up to three orders of magnitude speedup relative to a reference double loop Monte Carlo method.

关键词： Bayesian optimal experimental design Bayesian inverse problem Expected information gain Neural network Surrogate greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Collaborative strategic and tactical planning for one-way station-based carsharing systems with trip selection and vehicle relocation

引用

TRANSPORTATION LETTERS-THE INTERNATIONAL JOURNAL OF TRANSPORTATION RESEARCH 2023年第1期15卷 18-29页

作者： Wu, Jiayuan Hu, Lu Jiang, Yangsheng Southwest Jiaotong Univ Sch Transportat & Logist Chengdu 610031 Peoples R China Dept Southwest Jiaotong Univ Chengdu Peoples R China

Carsharing emerges as a flexible and sustainable transportation mode to deal with severe urban challenges. This paper addresses a joint design problem of carsharing systems by an integer linear programming (ILP) model. Strategic planning of stations' number, location and parking capacities and tactical planning of the fleet size and initial vehicle distribution are collaboratively optimized by considering all-day vehicle relocation and dynamic trip selection at the operational level. For the first time, vehicle relocation and demand selection are integrated with the joint optimization of strategic and tactical planning. We present a greedy heuristic algorithm embedding ILP to solve the problem. The case study of Chengdu demonstrates that the algorithm is computationally efficient when dealing with large-scale problems. The results identify how vehicle relocation and trip selection work in different scenes of travel time and demands and we conclude operators should target at medium-long trips by discount or promotion.

关键词： Carsharing location model trip selection vehicle relocation greedy algorithm integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Generation of Low-Delay and High-Stability Multicast Tree

引用

Computers, Materials & Continua 2023年第7期76卷 561-572页

作者： Deshun Li Zhenchen Wang Yucong Wei Jiangyuan Yao Yuyin Tan Qiuling Yang Zhengxia Wang Xingcan Cao School of Computer Science and Technology Hainan UniversityHaikouHainan570228China School of Cyberspace Security(School of Cryptology) Hainan UniversityHaikouHainan570228China Faculty of Arts University of British ColumbiaVancouverV6T1Z4Canada

Delay and stability are two key factors that affect the performance of multicast data transmission in a ***,current algorithms of tree generation hardly meet the requirements of low delay and high sta-bility *** a general network,the generation algorithm of a multicast tree with minimum delay and maximum stability is an NP-hard problem,without a precise and efficient *** address these challenges,this paper studies the generation of low-delay and high-stability multicast trees under the model of spanning tree based on stability probability,degree-constrained,edge-weighted for multicast(T-SDE).A class of algorithms was proposed which creates the multicast tree greedy on the ratio of fan-out to delay(RFD)and probability of stability of terminal to obtain a high performance in *** proposed algorithms greedily select terminals with a large RFD and a high probability of stability as forwarding nodes in the generation of the multicast tree,where the larger RFD and higher stability of upstream nodes are beneficial to achieve a low transmission delay and high stability in *** proposed RFD can be compatible with the original model,which can take advantage of network connectivity during the generation of a multicast *** paper carries out simulation experiments on Matlab R2016b to measure the performance of the proposed *** results show that the proposed algorithm can provide a smaller height,higher stability,and a lower transmission delay of the resulting multicast tree than other *** spanning tree of the proposed algorithms can support low transmission delay and high stability in multicast transmission.

关键词： Overlay network multicast tree transmission delay probability of stability greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

A novel algorithm for generating minimum energy points from identically charged particles in 1D, 2D and 3D unit hypercubes

引用

COMMUNICATIONS IN STATISTICS-SIMULATION AND COMPUTATION 2023年第8期52卷 3529-3552页

作者： Elsawah, A. M. Hua, Li Meng Fang, Kai-Tai Beijing Normal Univ Hong Kong Baptist Univ United Div Sci & Technol Zhuhai 519085 Peoples R China Zagazig Univ Fac Sci Dept Math Zagazig Egypt Chinasoft Int Co Shenzhen Peoples R China Chinese Acad Sci Key Lab Random Complex Struct & Data Anal Beijing Peoples R China

Generating minimum energy points (MEPs) is an optimal solution of many real-world problems, such as the selection of best locations for hospitals inside a city that reduce the overcrowding and competition and avoid the less-populated regions. The key idea is considering these locations as charged particles with the same sign (i.e., repel each other) inside a box and distribute these points by minimizing the total electric potential energy (TEPE) among them. The practice demonstrated that most of the existing techniques for generating MEPs are complex, especially for non-mathematicians. Therefore, the greedy algorithm (GreA) is the classical widely used algorithm for its simplicity even though a satisfactory result is not guaranteed. This paper gives a novel algorithm for generating MEPs from identically charged particles in 1D, 2D and 3D unit hypercubes. The results show that the new algorithm distributes the points far away from each other to reduce the TEPE of the generated MEPs more effectively than the GreA. The new algorithm is a significant improvement of the GreA to overcome its unsatisfactory results. Therefore, the new algorithm in its current form or after some improvements is highly recommended to be used instead of the GreA for many different applications.

关键词： DEoptim Electric field lines Electric potential energy Equipotential circles GenSA greedy algorithm Minimum energy points PSO Representative points 1 00940 1 00950 1 00990

来源：评论

学校读者我要写书评

暂无评论

Closed paths in graphs vs. voting theory

引用

THEORY AND DECISION 2024年第3期97卷 455-483页

作者： Saari, Donald G. Univ Calif Irvine Irvine CA 92697 USA

Features of graphs that hinder finding closed paths with particular properties, as represented by the Traveling Salesperson Problem-TSP, are identified for three classes of graphs. Removing these terms leads to a companion graph with identical closed path properties that is easier to analyze. A surprise is that these troubling graph factors are precisely what is needed to analyze certain voting methods, while the companion graph's terms are what cause voting theory complexities as manifested by Arrow's Theorem. This means that the seemingly separate goals of analyzing closed paths in graphs and analyzing voting methods are complementary: components of data terms that assist in one of these areas are the source of troubles in the other. Consequences for standard decision methods are in Sects. 2.5, 3.7 and the companion paper (Saari in Theory Decis 91(3):377-402, 2021). The emphasis here is on paths in graphs;incomplete graphs are similarly handled.

关键词： TSP Hamiltonian circuits greedy algorithm Closed path symmetries Transitive rankings

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：