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

Defending Against Malicious Influence Control in Online Leader-Follower Social Networks

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2024年 19卷 4809-4819页

作者： Zhu, Liwang Zhou, Xiaotian Tian, Jiahe Li, Wei Zhang, Zhongzhi Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China Fudan Univ Acad Engn & Technol Shanghai 200433 Peoples R China Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China Fudan Univ Res Inst Intelligent Complex Syst Shanghai 200433 Peoples R China

The formation of opinions is fundamentally a network-based process, where the opinions of individuals in a social network exchange, evolve, and eventually converge towards a specific distribution. However, this dynamic process may be susceptible to manipulation by adversarial entities, who aim to maliciously influence the opinion formulation. The adversary may engage in extensive influence campaigns, disseminating misinformation among populations, thereby potentially destabilizing societies. It is thus of significance to develop strategies to defend against such attacks, which are essential for fostering a healthy environment for information sharing, social deliberation, and opinion formation. In this paper, we investigate a scenario wherein an external adversary aims to maliciously alter the opinions of a general social graph. This is achieved by targeting several selected nodes, referred to as followers. Concurrently, we explore a counter-strategy, aiming to negate the influence of the adversary with malicious intents. This involves identifying a subset of nodes to act as followers of a defending leader, thereby minimizing the adversary's impact. Since this problem can be framed as a non-increasing supermodular minimization problem, we develop a $(1-1/e)$ approximation greedy algorithm consequently. Moreover, to overcome the computation challenge for large-scale networks, we establish an efficient approximation to the key quantity of the greedy algorithm. This refinement significantly enhances computational efficiency and scalability, making the algorithm applicable to networks with millions of nodes. Extensive simulation results on various real-world networks demonstrate the superior performance of our improved algorithm over existing algorithms and other baseline schemes based on centrality measures. In particular, our improved algorithm scales to networks of considerable size, with negligible sacrifice on the quality of solutions.

关键词： Opinion dynamics leader-follower social networks graph algorithm malicious influence control discrete optimization defense strategies

来源：评论

学校读者我要写书评

暂无评论

Minimum edge ranking spanning trees of split graphs

引用

DISCRETE APPLIED MATHEMATICS 2006年第16期154卷 2373-2386页

作者： Makino, Kazuhisa Uno, Yushi Ibaraki, Toshihide Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan Univ Tokyo Grad Sch Informat & Technol Dept Math Informat Tokyo 1138656 Japan Kwansei Gakuin Univ Sch Sci & Technol Dept Informat Sanda 6691337 Japan

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split. (c) 2006 Elsevier B.V. All rights reserved.

关键词： edge ranking minimum edge ranking spanning tree split graphs threshold graphs graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving path problems on the GPU

引用

PARALLEL COMPUTING 2010年第5-6期36卷 241-253页

作者： Buluc, Aydin Gilbert, John R. Budak, Ceren Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

We consider the computation of shortest paths on graphic Processing Units (GPUs). The blocked recursive elimination strategy we use is applicable to a class of algorithms (such as all-pairs shortest-paths, transitive closure, and LU decomposition without pivoting) having similar data access patterns. Using the all-pairs shortest-paths problem as an example, we uncover potential gains over this class of algorithms. The impressive computational power and memory bandwidth of the CPU make it an attractive platform to run such computationally intensive algorithms. Although improvements over CPU implementations have previously been achieved for those algorithms in terms of raw speed, the utilization of the underlying computational resources was quite low. We implemented a recursively partitioned all-pairs shortest-paths algorithm that harnesses the power of GPUs better than existing implementations. The alternate schedule of path computations allowed us to cast almost all operations into matrix-matrix multiplications on a semiring. Since matrix-matrix multiplication is highly optimized and has a high ratio of computation to communication, our implementation does not suffer from the premature saturation of bandwidth resources as iterative algorithms do. By increasing temporal locality, our implementation runs more than two orders of magnitude faster on an NVIDIA 8800 CPU than on an Opteron. Our work provides evidence that programmers should rethink algorithms instead of directly porting them to CPU. (C) 2009 Elsevier By. All rights reserved.

关键词： All-pairs shortest-paths Gaussian elimination graphical processing unit Semiring Matrix multiplication graph algorithm Shortest path Linear algebra

来源：评论

学校读者我要写书评

暂无评论

An efficient exact algorithm for constraint bipartite vertex cover

引用

JOURNAL OF algorithmS-COGNITION INFORMATICS AND LOGIC 2001年第2期38卷 374-410页

作者： Fernau, H Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

The constraint bipatite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k(1), k(2), is there a vertex cover taking at most k(1) vertices from one and at most k(2) vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999(k1+k2) + (k(1) + k(2))n) time. Our algorithm is efficient and practical for small values of k(1) and k(2), as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed;nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths land hence the depth of the search tree as a whole) by a sort of bonus points. (C) 2001 academic Press.

关键词： NP-complete problem graph algorithm VLSI vertex cover fixed parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

An 8-approximation algorithm for L(2,1)-labeling of unit disk graphs

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期341卷 93-101页

作者： Ono, Hirotaka Yamanaka, Hisato Nagoya Univ Grad Sch Informat Dept Math Informat Chikusa ku Nagoya Aichi 4648601 Japan Kozo Keikaku Engn Inc 4-5-3 Chuo Nakano ku Tokyo 1640011 Japan

Given a graph G = (V, E), an L(2, 1)-labeling of the graph is an assignment l from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), vertical bar l(u) - l(v)vertical bar >= 2 if u and v are adjacent, and l(u) not equal l(v) if u and v are at distance 2. The L(2, 1)-labeling problem is to minimize the range of l (i.e., max(u is an element of V)(l(u))-min(u is an element of V)(l(u))+ 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L(2, 1)-labeling of unit disk graphs. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Frequency/channel assignment graph algorithm Distance-constrained labeling L(2,1)-labeling Approximation algorithm Unit disk graph

来源：评论

学校读者我要写书评

暂无评论

Polymatroid-based capacitated packing of branchings

引用

DISCRETE APPLIED MATHEMATICS 2019年 270卷 190-203页

作者： Matsuoka, Tatsuya Szigeti, Zoltan NEC Corp Ltd Nakahara Ku 1753 Shimonumabe Kawasaki Kanagawa Japan Univ Grenoble Alpes CNRS Grenoble INP G SCOP 46 Ave Felix Viallet Grenoble France

Edmonds (1973) characterized the condition for the existence of a packing of spanning arborescences and also that of spanning branchings in a directed graph. Durand de Gevigney, Nguyen and Szigeti (2013) generalized the spanning arborescence packing problem to a matroid-based arborescence packing problem and gave a necessary and sufficient condition for the existence of a packing and a polynomial-time algorithm. In this paper, a generalization of this latter problem - the polymatroid-based arborescence packing problem - is considered. Two problem settings are formulated: an unsplittable version and a splittable version. The unsplittable version is shown to be strongly NP-complete. Whereas, the splittable version, which generalizes the capacitated version of the spanning arborescence packing problem, can be solved in strongly polynomial time. For convenience, we provide a strongly polynomial-time algorithm for the problem of the polymatroid-based capacitated packing of branchings for the splittable version. (C) 2019 Elsevier B.V. All rights reserved.

关键词： graph algorithm Arborescence packing Polymatroid Arc capacity

来源：评论

学校读者我要写书评

暂无评论

On Coloring Rectangular and Diagonal Grid graphs for Multipatterning and DSA Lithography

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2020年第6期39卷 1205-1216页

作者： Guo, Daifeng Zhang, Hongbo Wong, Martin D. F. Univ Illinois Dept Elect & Comp Engn Champaign IL 61801 USA Facebook Inc Dept Engn Menlo Pk CA 94025 USA

Rectangular grid graph (RGG) and diagonal grid graph (DGG) are induced subgraphs of a rectangular or diagonal grid, respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multipatterning lithography (MPL). However, the problem in general is computationally difficult for k > 2, while it remains an open question on grid graphs due to their regularity and sparsity. On the other hand, directed self-assembly (DSA) technique can work with MPL to optimize the graph by grouping neighboring vertices such that k can be reduced, but the problem of deploying the grouping for coloring is even more intractable. In this paper, we study both of the k-coloring problems, with and without DSA grouping, on RGG and DGG. Without grouping, a complete k-coloring analysis is conducted and particularly the NP-completeness of 3-coloring on a diagonal grid is proved. When considering grouping, we present a 3-coloring solution and prove the NP-completeness to solve the problem of k = 2.

关键词： Design for manufacturing (DFM) directed self-assembly (DSA) graph algorithm grid graph k-coloring multiple patterning lithography (MPL)

来源：评论

学校读者我要写书评

暂无评论

algorithms for graphs with small octopus

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期134卷 105-128页

作者： Fomin, FV Kratsch, D Müller, H Univ Bergen Dept Informat N-5020 Bergen Norway Univ Metz Lab Informat Theor & Appliquee F-57045 Metz 01 France Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England

A d-octopus of a graph G = (V, E) is a subgraph T = (W, F) of G such that W is a dominating set of G, and T is the union of d (not necessarily disjoint) shortest paths of G that have one endpoint in common. First, we study the complexity of finding and approximating a d-octopus of a graph. Then we show that for some NP-complete graph problems that are hard to approximate in general there are efficient approximation algorithms with worst case performance ratio c . d for some small constant c > 0 (depending on the problem) assuming that the input graph G is given together with a d-octopus of G. For example, there is a linear time algorithm to approximate the bandwidth of a graph within a factor of 8d. Furthermore, the minimum number of subsets in a partition of the vertex set of a graph into clusters of diameter at most k can be approximated in linear time within a factor of 3d (for k = 2) and 2d (for k greater than or equal to 3). Finally, we show that there are O(n(7d+2)) time algorithms to compute a minimum cardinality dominating set, respectively, total dominating set for graphs having a d-octopus. (C) 2003 Elsevier B.V. All rights reserved.

关键词： approximation algorithm graph algorithm bandwidth clustering lambda-coloring bilateral orientation domination

来源：评论

学校读者我要写书评

暂无评论

First Fast Sink: A compiler algorithm for barrier placement optimisation

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 1998年第4-5期13卷 397-406页

作者： Stohr, EA O'Boyle, MFP Univ Manchester Dept Comp Sci Manchester M13 9PL Lancs England Univ Edinburgh Dept Comp Sci Edinburgh EH9 3JZ Midlothian Scotland

This paper describes a new compiler algorithm to reduce the number of barrier synchronisations in parallelised programs. A preliminary technique to rapidly determine critical data dependences is developed. This forms the basis of the First Fast Sink (FFS) algorithm which places, provably, the minimal number of barriers in polynomial time for codes with a regular structure. This algorithm is implemented in a prototype compiler and applied to three well known benchmarks. Preliminary results show that it outperforms an existing state-of-the-art commercial compiler. Copyright (C) 1998 Elsevier Science B.V.

关键词： barrier synchronisation optimising compilation graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter

引用

THEORETICAL COMPUTER SCIENCE 2019年 770卷 69-78页

作者： Le, Hoang-Oanh Le, Van Bang Univ Rostock Inst Informat Rostock Germany

In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP complete even when restricted to bipartite graphs. It has been proved that MATCHING CUT is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d >= 3, MATCHING CUT is NP-complete in the class of graphs of diameter d. This resolves an open problem posed by Borowiecki and Jesse-Jozefczyk (2008) [6]. We then show that, for any fixed integer d >= 4, MATCHING CUT is NP-complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that MATCHING CUT is polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving MATCHING CUT in graphs of diameter 2. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Matching cut NP-hardness graph algorithm Computational complexity Dichotomy theorem Decomposable graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：