RTG: a recursive realistic graph generator using random typing

We propose a new, recursive model to generate realistic graphs, evolving over time. Our model has the following properties: it is (a) flexible, capable of generating the cross product of weighted/unweighted, directed/undirected, uni/bipartite graphs; (b) realistic, giving graphs that obey eleven static and dynamic laws that real graphs follow (we formally prove that for several of the (power) laws and we estimate their exponents as a function of the model parameters); (c) parsimonious, requiring only four parameters. (d) fast, being linear on the number of edges; (e) simple, intuitively leading to the generation of macroscopic patterns. We empirically show that our model mimics two real-world graphs very well: Blognet (unipartite, undirected, unweighted) with 27 K nodes and 125 K edges; and Committee-to-Candidate campaign donations (bipartite, directed, weighted) with 23 K nodes and 880 K edges. We also show how to handle time so that edge/weight additions are bursty and self-similar.     

A branch‐and‐price approach to k‐clustering minimum biclique completion problem

We consider the problem of finding k‐bipartite subgraphs, called “clusters,” in a bipartite graph , such that each vertex i of S appears in exactly one of the subgraphs, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and the total number of edges needed to complete each cluster (i.e. to become a biclique) is minimized. This problem has been shown to be strongly NP‐hard and is known as the k‐clustering minimum biclique completion problem. It has been applied to bundling channels for multicast transmissions. The application consists of finding k‐multicast sessions that partition the set of demands, given a set of demands of services from clients. Each service should belong to a single multicast session, while each client can appear in more than one session. We extend previous work by developing a branch‐and‐price algorithm that embeds a new metaheuristic based on variable neighborhood infeasible search and a branching rule that exploits the problem structure. The metaheuristic can also efficiently solve the pricing subproblem. In addition to the random instances used in the literature, we present structured instances generated using the MovieLens dataset collected by the GroupLens Research Project. Extensive computational results show that our branch‐and‐price algorithm outperforms the approaches proposed in the literature.     

Multiscale Visualization and Exploration of Large Bipartite Graphs

A bipartite graph is a powerful abstraction for modeling relationships between two collections. Visualizations of bipartite graphs allow users to understand the mutual relationships between the elements in the two collections, e.g., by identifying clusters of similarly connected elements. However, commonly‐used visual representations do not scale for the analysis of large bipartite graphs containing tens of millions of vertices, often resorting to an a‐priori clustering of the sets. To address this issue, we present the Who's‐Active‐On‐What‐Visualization (WAOW‐Vis) that allows for multiscale exploration of a bipartite social‐network without imposing an a‐priori clustering. To this end, we propose to treat a bipartite graph as a high‐dimensional space and we create the WAOW‐Vis adapting the multiscale dimensionality‐reduction technique HSNE. The application of HSNE for bipartite graph requires several modifications that form the contributions of this work. Given the nature of the problem, a set‐based similarity is proposed. For efficient and scalable computations, we use compressed bitmaps to represent sets and we present a novel space partitioning tree to efficiently compute similarities; the Sets Intersection Tree. Finally, we validate WAOW‐Vis on several datasets connecting Twitter‐users and ‐streams in different domains: news, computer science and politics. We show how WAOW‐Vis is particularly effective in identifying hierarchies of communities among social‐media users.     

Bipartite Linear χ‐Consensus of Double‐Integrator Multi‐Agent Systems With Measurement Noise

The bipartite consensus problem is investigated for double‐integrator multi‐agent systems in the presence of measurement noise. A distributed protocol with time‐varying consensus gain is proposed. By using tools of state transition matrix and algebraic graph theory, necessary and sufficient conditions for the designed protocol to be a mean square bipartite linear χ‐consensus protocol are given. It is shown that the signed digraph being structurally balanced and having a spanning tree are not only sufficient, but also necessary for bipartite consensus. Furthermore, the protocol is proved to be a mean square bipartite average consensus protocol if the signed graph is weight balanced.     

Smallest Bipartite Bridge-Connectivity Augmentation

This paper addresses two augmentation problems related to bipartite graphs. The first, a fundamental graph-theoretical problem, is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, and still bipartite. The second problem, which arises naturally from research on the security of statistical data, is how to add edges so that the resulting graph is simple and does not contain any bridges. In both cases, after adding edges, the graph can be either a simple graph or, if necessary, a multi-graph. Our approach then determines whether or not such an augmentation is possible. We propose a number of simple linear-time algorithms to solve both problems. Given the well-known bridge-block data structure for an input graph, the algorithms run in O(log n) parallel time on an EREW PRAM using a linear number of processors, where n is the number of vertices in the input graph. We note that there is already a polynomial time algorithm that solves the first augmentation problem related to graphs with a given general partition constraint in O(n(m+nlog n)log n) time, where m is the number of distinct edges in the input graph. We are unaware of any results for the second problem. H.-W. Wei, W.-C. Lu and T.-s. Hsu research supported in part by NSC of Taiwan Grants 94-2213-E-001-014, 95-2221-E-001-004 and 96-2221-E-001-004.     

Restrictions of Minimum Spanner Problems

At-spanner of a graphGis a spanning subgraphHsuch that the distance between any two vertices inHis at mostttimes their distance inG. Spanners arise in the context of approximating the original graph with a sparse subgraph (Peleg, D., and Schäffer, A. A. (1989),J. Graph. Theory13(1), 99–116). The MINIMUMt-SPANNER problem seeks to find at-spanner with the minimum number of edges for the given graph. In this paper, we completely settle the complexity status of this problem for various values oft, on chordal graphs, split graphs, bipartite graphs and convex bipartite graphs. Our results settle an open question raised by L. Cai (1994,Discrete Appl. Math.48, 187–194) and also greatly simplify some of the proofs presented by Cai and by L. Cai and M. Keil (1994,Networks24, 233–249). We also give a factor 2 approximation algorithm for the MINIMUM 2-SPANNER problem on interval graphs. Finally, we provide approximation algorithms for the bandwidth minimization problem on convex bipartite graphs and split graphs using the notion of tree spanners.     

A diagrammatic classification in a combinatorial problem: the case of the stable marriage problem

The stable marriage problem (SMP) is a combinatorial problem to find stable matching between n women and n men given a complete preference list of men over women and vice versa. An instance of the SMP can be expressed by a bipartite graph with multiple (weighted) edges. By rearranging the graph, we use a diagram that involves several constraints to visualize several symmetries. By the diagram, all instances of the size-three SMP (three women and three men) are classified. The classification may be supported by the fact that the same class has the same stable matching.     

Distributed edge coloration for bipartite networks

This paper presents a self-stabilizing algorithm to color the edges of a bipartite network such that any two adjacent edges receive distinct colors. The algorithm has the self-stabilizing property; it works without initializing the system. It also works in a de-centralized way without a leader computing a proper coloring for the whole system. Moreover, it finds an optimal edge coloring and its time complexity is O(n ² k + m) moves, where k is the number of edges that are not properly colored in the initial configuration. This is a completely revised and extended version of [15]. This research was supported in part by the National Science Council of the Republic of China under the Contract NSC94-2213-E008-001.     

Finding Maximum Induced Matchings in Subclasses of Claw-Free and <Emphasis Type="Italic">P</Emphasis><Subscript>5</Subscript>-Free Graphs,and in Graphs with Matching and Induced Matching of Equal Maximum Size

In a graph G a matching is a set of edges in which no two edges have a common endpoint. An induced matching is a matching in which no two edges are linked by an edge of G. The maximum induced matching (abbreviated MIM) problem is to find the maximum size of an induced matching for a given graph G. This problem is known to be NP-hard even on bipartite graphs or on planar graphs. We present a polynomial time algorithm which given a graph G either finds a maximum induced matching in G, or claims that the size of a maximum induced matching in G is strictly less than the size of a maximum matching in G. We show that the MIM problem is NP-hard on line-graphs, claw-free graphs, chair-free graphs, Hamiltonian graphs and r-regular graphs for r \geq 5. On the other hand, we present polynomial time algorithms for the MIM problem on (P ₅,D _m )-free graphs, on (bull, chair)-free graphs and on line-graphs of Hamiltonian graphs.     

Decomposition of graphs and monotone formula size of homogeneous functions

Summary We show that every graph on n nodes can be partitioned by a number of complete bipartite graphs with O(n ²/log n) nodes with no edge belonging to two of them. Since each partition corresponds directly to a monotone formula for the associated quadratic function we obtain an upper bound for the monotone formula size of quadratic functions. Our method extends to uniform hypergraphs with fixed range and thus to homogeneous functions with fixed length of prime implicants. Finally we give an example of a quadratic function where each monotone formula built from arbitrary partitions of the graph (double edges allowed) is not optimal. That means we disprove the single-level-conjecture for formulae.     

A framework for development of fuzzy GOMS model for human‐computer interaction

The objective of this study was to examine usefulness of fuzzy methodologies in the analysis and design of human‐computer interaction. A framework for generalization of the Goals‐Operators‐Methods‐Selection Rules (GOMS) model, and its fuzzy version was proposed. An experimental verification of the fuzzy GOMS model was also provided. A total of six subjects participated in two laboratory experiments. These experiments were performed in order to validate the proposed fuzzy GOMS model for the text editing task described in information processing terms. The subjects were not familiar with the text files to be edited, and the task was performed from the subject's own office and desk. All subjects were familiar with and regularly used the VI screen editor. The experiments consisted of the following steps: (1) the subject performed a familiar text editing task using a screen editor (VI); (2) the methods by which the subject achieved his goals (word location) as well as selection rules were elicited; (3) several compatibility functions for fuzzy terms used by the subject were derived; and (4) once all the rules, methods, and corresponding membership functions have been elicited, the theory of possibility was used to model the expert's rule selection process. For this purpose, each of the potential rules was assigned a possibility measure equal to the membership value(s) derived during the elicitation phase of experiment Finally, the selected methods were compared to non‐fuzzy predictions and actual experimental data. It was shown that overall, across all subjects and trials of the main editing task, the fuzzy‐based COMS model predicted significantly more of the subject responses, than did the non‐fuzzy COMS model.     

A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem

Given a graph with its vertex set partitioned into a set of groups, nonnegative costs associated to its edges, and nonnegative prizes associated to its vertices, the prize‐collecting generalized minimum spanning tree problem consists in finding a subtree of this graph that spans exactly one vertex of each group and minimizes the sum of the costs of the edges of the tree less the prizes of the selected vertices. It is a generalization of the NP‐hard generalized minimum spanning tree optimization problem. We propose a GRASP (greedy randomized adaptive search procedure) heuristic for its approximate solution, incorporating path‐relinking for search intensification and a restart strategy for search diversification. The hybridization of the GRASP with path‐relinking and restarts heuristic with a data mining strategy that is applied along with the GRASP iterations, after the elite set is modified and becomes stable, contributes to making the heuristic more robust. The computational experiments show that the heuristic developed in this work found very good solutions for test problems with up to 439 vertices. All input data for the test instances and detailed numerical results are made available from Mendeley Data.     

基于k-频繁子图聚类的二分图匿名方法

针对以二分图形式发布的社会网络隐私泄露问题,提出了一种面向敏感边识别攻击的社会网络二分图匿名方法。在已有k-安全分组的理论基础上,结合二分图的稀疏性和敏感边识别攻击形式,分别提出了正单向、逆单向以及完全（c1,c2）-安全性原则,并在此基础上,形式化地定义了一类抗敏感边识别攻击的社会网络二分图安全匿名问题;同时,还提出了一种基于k-频繁子图聚类的二分图划分算法和一种基于二分图（c1,c2）-安全性的匿名算法来保证发布二分图的安全性。实验结果表明,该算法在与已有方法相当时间开销的前提下,能产生更小的信息损失度,有效地抵制了敏感边识别攻击,实现了二分图的安全发布。     

A New QEM for Parametrization of Raster Images

We present an image processing method that converts a raster image to a simplical two‐complex which has only a small number of vertices (base mesh) plus a parametrization that maps each pixel in the original image to a combination of the barycentric coordinates of the triangle it is finally mapped into. Such a conversion of a raster image into a base mesh plus parametrization can be useful for many applications such as segmentation, image retargeting, multi‐resolution editing with arbitrary topologies, edge preserving smoothing, compression, etc. The goal of the algorithm is to produce a base mesh such that it has a small colour distortion as well as high shape fairness, and a parametrization that is globally continuous visually and numerically. Inspired by multi‐resolution adaptive parametrization of surfaces and quadric error metric, the algorithm converts pixels in the image to a dense triangle mesh and performs error‐bounded simplification jointly considering geometry and colour. The eliminated vertices are projected to an existing face. The implementation is iterative and stops when it reaches a prescribed error threshold. The algorithm is feature‐sensitive, i.e. salient feature edges in the images are preserved where possible and it takes colour into account thereby producing a better quality triangulation.     

Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes unique. The Isolation Lemma as described in Mulmuley et al. (Combinatorica 7(1):105–131, 1987) achieves the same for general graphs using randomness, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the perfect matching problem in bipartite planar graphs to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a highly parallel SPL\mathsf{SPL} algorithm for both decision and construction versions of the bipartite perfect matching problem. This improves the earlier known bounds of non-uniform SPL\mathsf{SPL} by Allender et al. (J. Comput. Syst. Sci. 59(2):164–181, 1999) and NC\mathsf{NC} ² by Miller and Naor (SIAM J. Comput. 24:1002–1017, 1995), and by Mahajan and Varadarajan (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 351–357, 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Further we try to find the lower bound on the number of bits needed for deterministically isolating a perfect matching. We show that our particular method for isolation will require Ω(log n) bits. Our techniques are elementary.     

Component‐wise Controllers for Structure‐Preserving Shape Manipulation

Recent shape editing techniques, especially for man‐made models, have gradually shifted focus from maintaining local, low‐level geometric features to preserving structural, high‐level characteristics like symmetry and parallelism. Such new editing goals typically require a pre‐processing shape analysis step to enable subsequent shape editing. Observing that most editing of shapes involves manipulating their constituent components, we introduce component‐wise controllers that are adapted to the component characteristics inferred from shape analysis. The controllers capture the natural degrees of freedom of individual components and thus provide an intuitive user interface for editing. A typical model usually results in a moderate number of controllers, allowing easy establishment of semantic relations among them by automatic shape analysis supplemented with user interaction. We propose a component‐wise propagation algorithm to automatically preserve the established inter‐relations while maintaining the defining characteristics of individual controllers and respecting the user‐specified modeling constraints. We extend these ideas to a hierarchical setup, allowing the user to adjust the tool complexity with respect to the desired modeling complexity. We demonstrate the effectiveness of our technique on a wide range of man‐made models with structural features, often containing multiple connected pieces.     

An Efficient Algorithm for Batch Stability Testing

Given a stable marriage problem instance represented by a bipartite graph having 2n vertices and m edges, we describe an algorithm that can verify the stability of k different matchings in a batch fashion in O((m+kn)log ² n) time. This affirmatively answers a longstanding open question of Gusfield and Irving as to whether stability can be verified in a batch setting (after sufficient preprocessing) in time sub-quadratic in n.     

Bipartite tracking of homogeneous and heterogeneous linear multi-agent systems

In this paper, we consider bipartite tracking of linear multi-agent systems with a leader. Both homogeneous and heterogeneous systems are investigated. The communication between agents is modelled by a directed signed graph, where the negative (positive) edges represent the antagonistic (cooperative) interactions among agents. Linear Quadratic Regulator (LQR)-based approach is used to derive the distributed protocol for the follower agent to achieve bipartite tracking of the leader. It is shown that solving the bipartite tracking problem over the structurally balanced signed graph is equivalent to solving the cooperative tracking problem over a corresponding graph with nonnegative edge weights. This bridges the gap between the newly raised bipartite tracking problem and the well-studied cooperative tracking problem. Three novel control protocols are proposed for both cooperative and bipartite output tracking of heterogeneous linear multi-agent systems. Numerical examples are given to show the effectiveness of our control protocols.     

A GRASP heuristic using path‐relinking and restarts for the Steiner traveling salesman problem

The traveling salesman problem (TSP) is one of the most studied problems in combinatorial optimization. Given a set of nodes and the distances between them, it consists in finding the shortest route that visits each node exactly once and returns to the first. Nevertheless, more flexible and applicable formulations of this problem exist and can be considered. The Steiner TSP (STSP) is a variant of the TSP that assumes that only a given subset of nodes must be visited by the shortest route, eventually visiting some nodes and edges more than once. In this paper, we adapt some classical TSP constructive heuristics and neighborhood structures to the STSP variant. In particular, we propose a reduced 2‐opt neighborhood and we show that it leads to better results in smaller computation times. Computational results with an implementation of a GRASP heuristic using path‐relinking and restarts are reported. In addition, ten large test instances are generated. All instances and their best‐known solutions are made available for download and benchmarking purposes.     

Scheduling with Conflicts on Bipartite and Interval Graphs

In this paper, we consider the on-line scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that the set of all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. Our results focus on two special classes of graphs motivated by our applications: bipartite graphs and interval graphs. The cost function we use is maximum response time. In all of the upper bounds, we devise algorithms which maintain a set of invariants which bound the accumulation of jobs on cliques (in the case of bipartite graphs, edges) in the graph. The lower bounds show that the invariants maintained by the algorithms are tight to within a constant factor. For a specific graph which arises in the traffic intersection control problem, we show a simple algorithm which achieves the optimal competitive ratio.