Multilayer grid embeddings for VLSI

In this paper we propose two new multilayer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes “exist” only on one layer, we prove a tight area × (number of contact cuts) = Θ(n ²) tradeoff for embeddingn-node planar graphs of bounded degree in two layers. For the second model in which nodes “exist” simultaneously on all layers, we give a number of upper bounds on the area needed to embed groups using no contact cuts. We show that anyn-node graph of thickness 2 can be embedded on two layers inO(n ²) area. This bound is tight even if more layers and any number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers inO(n ^3/2(logn)²) area. Some of our embedding algorithms have the additional property that they can respect prespecified grid placements of the nodes of the graph to be embedded. We give an algorithm for embeddingn-node graphs of thicknessk ink layers usingO(n ³) area, using no contact cuts, and respecting prespecified node placements. This area is asymptotically optimal for placement-respecting algorithms, even if more layers are allowed, as long as a fixed fraction of the edges do not use contact cuts. Our results use a new result on embedding graphs in a single-layer grid, namely an embedding ofn-node planar graphs such that each edge makes at most four turns, and all nodes are embedded on the same line.     

Network visualization with Nam, the VINT network animator

Network protocol designers face many difficult tasks, including simultaneously monitoring state in a potentially large number of nodes, understanding and analyzing complex message exchanges, and characterizing dynamic interactions with competing traffic. Traditionally they have used packet traces to accomplish these tasks, but traces have two major drawbacks: they present an incredible amount of detail, which challenges the designer's ability to comprehend the data; and they are static, which hides an important dimension of protocol behavior. As a result, detailed analysis frequently becomes tedious and error-prone. Although network simulators such as the VINT project's ns can easily generate numerous detailed traces, they provide limited help for analyzing and understanding the data. Nam, the network animator that we developed in our work at the VINT project, provides packet-level animation, protocol graphs, traditional time-event plots of protocol actions, and scenario editing capabilities. Nam benefits from a close relationship with ns, which can collect detailed protocol information from a simulation. With some preprocessing. Nam can visualize data taken directly from real network traces     

Conditional Fault Diameter of Star Graph Networks

It is well known that star graphs are strongly resilient like thencubes in the sense that they are optimally fault tolerant and the fault diameter is increased only by one in the presence of maximum number of allowable faults. We investigate star graphs under the conditions offorbidden faulty sets, where all the neighbors of any node cannot be faulty simultaneously; we show that under these conditions star graphs can tolerate upto (2n− 5) faulty nodes and the fault diameter is increased only by 2 in the worst case in presence of maximum number of faults. Thus, star graphs enjoy the similar property of strong resilience under forbidden faulty sets like then-cubes. We have developed algorithms to trace the vertex disjoint paths under different conditions.     

面向时序图数据的快速环枚举算法

时序图数据是一类边上带有时间戳信息的图数据.在时序图数据中,时序环是边满足时间戳递增约束的回路.时序环枚举在现实中有着很多应用,它可以帮助挖掘金融网络中的欺诈行为.此外,研究时序环的数量对于刻画不同时序图的特性也有重要作用.基于2018年由Rohit Kumar等人提出的时序环枚举算法（2SCENT算法）,提出一种通过添加环路信息来削减搜索空间的新型时序环枚举算法.所提出的算法为一个两阶段的算法：1）首先,通过遍历原图获得所有可能会形成环路的节点,以及相应的时间和长度信息;2）然后,利用以上信息进行动态深度优先搜索,挖掘所有的满足约束条件的环.在4个不同的真实时序图数据集上进行了大规模的实验,并以2SCENT算法作为基准对算法进行了对比.实验结果表明,所提出的算法较之前最好的2SCENT算法要快50%以上.     

基于虚拟力的混合感知网节点部署

感知网一般是由静态的或移动的节点组成,为保证感知网的感知功能,节点应该有自部署和自修复能力.然而全部由移动传感器组成的感知网的成本太高,为保证感知网的覆盖功能和低成本,提出了一种在静态传感器节点中加入移动传感器节点的混合感知网形式.为了更好地部署这些节点,最大化覆盖待感知区域,提出了一种基于节点间虚拟力的移动节点部署方法,利用静态节点和移动节点以及移动节点之间的虚拟人工势场产生的作用力来控制移动节点的运动,使移动节点能够在较短的时间内,以较少的能量消耗到达自己合适的位置.在理论上分析了算法的可行性,用仿真实验验证了此算法的有效性,并和其他3种类似算法进行了性能比较.     

Inferring Contagion Patterns in Social Contact Networks with Limited Infection Data

The spread of infectious disease is an inherently stochastic process. As such, real time control and prediction methods present a significant challenge. For diseases which spread through direct human interaction, (e.g., transferred from infected to susceptible individuals) the contagion process can be modeled on a social-contact network where individuals are represented as nodes, and contacts between individuals are represented as links. The model presented in this paper seeks to identify the infection pattern which depicts the current state of an ongoing outbreak. This is accomplished by inferring the most likely paths of infection through a contact network under the assumption of partially available infection data. The problem is formulated as a bi-linear integer program, and heuristic solution methods are developed based on sub-problems which can be solved much more efficiently. The heuristic performance is presented for a range of randomly generated networks and different levels of information. The model results, which include the most likely set of infection spreading contacts, can be used to provide insight into future epidemic outbreak patterns, and aid in the development of intervention strategies.     

LAD: Localization anomaly detection for wireless sensor networks

In wireless sensor networks (WSNs), sensors’ locations play a critical role in many applications. Having a GPS receiver on every sensor node is costly. In the past, a number of location discovery (localization) schemes have been proposed. Most of these schemes share a common feature: they use some special nodes, called beacon nodes, which are assumed to know their own locations (e.g., through GPS receivers or manual configuration). Other sensors discover their locations based on the reference information provided by these beacon nodes. Most of the beacon-based localization schemes assume a benign environment, where all beacon nodes are supposed to provide correct reference information. However, when the sensor networks are deployed in a hostile environment, where beacon nodes can be compromised, such an assumption does not hold anymore. In this paper, we propose a general scheme to detect localization anomalies that are caused by adversaries. Our scheme is independent from the localization schemes. We formulate the problem as an anomaly intrusion detection problem, and we propose a number of ways to detect localization anomalies. We have conducted simulations to evaluate the performance of our scheme, including the false positive rates, the detection rates, and the resilience to node compromises.     

一种新的高效图聚集算法

图聚集是将一个大规模的图用简洁的并能有效反映原始图的结构和属性信息的小规模图来表示的技术.图聚集在图数据管理、分析和可视化中发挥着重要作用.图聚集方面现有研究结果还很少,也很不系统.其主要不足之处是:1)算法依赖于具体应用;2)算法仅考虑了图的某方面信息,如结构信息或属性信息;3)算法对用户提供的交互和反馈信息的约束很强.针对现有图聚集算法存在的主要不足,提出一种有向图新型图聚集算法,该算法采用一种新的聚集图质量函数,全面刻画了聚集图多样性、覆盖性、简洁性和实用性.该算法使用LSH(locality sensitive Hashing)技术和基于熵的划分技术,保证了聚集图的质量.在真实数据集上进行了大量的实验,验证了算法的有效性.     

DiDuSoNet: A P2P architecture for distributed Dunbar-based social networks

Online Social Networks (OSNs) are becoming more and more popular on the Web. Distributed Online Social Networks (DOSNs) are OSNs which do not exploit a central server for storing users data and enable users to have more control on their profile content, ensuring a higher level of privacy. In a DOSN there are some technical challenges to face. One of the most important challenges is the data availability problem when a user is offline. In this paper we propose DiDuSoNet, a novel P2P Distributed Online Social Network where users can exercise full access control on their data. Our system exploits trust relationships for providing a set of important social services, such as trustness, information diffusion, and data availability. In this paper we show how our system manages the problem of data availability by proposing a new P2P dynamic trusted storage approach. By following the Dunbar concept, our system stores the data of a user only on a restricted number of friends which have regular contacts with him/her. Differently from other approaches, nodes chosen to keep data replicas are not statically defined but dynamically change according to users churn. In according to our previous work, we use only two online profile replicas at time. By using real Facebook data traces we prove that our approach offers high availability.     

A general framework for relation graph clustering

Relation graphs, in which multi-type (or single type) nodes are related to each other, frequently arise in many important applications, such as Web mining, information retrieval, bioinformatics, and epidemiology. In this study, We propose a general framework for clustering on relation graphs. Under this framework, we derive a family of clustering algorithms including both hard and soft versions, which are capable of learning cluster patterns from relation graphs with various structures and statistical properties. A number of classic approaches on special cases of relation graphs, such as traditional graphs with singly-type nodes and bi-type relation graphs with two types of nodes, can be viewed as special cases of the proposed framework. The theoretic analysis and experiments demonstrate the great potential and effectiveness of the proposed framework and algorithm.     

Information diffusion in distributed OSN: The impact of trusted relationships

Distributed Online Social Networks (DOSN) are a valid alternative to OSN based on peer-to-peer communications. Without centralised data management, DOSN must provide the users with higher level of control over their personal information and privacy. Thus, users may wish to restrict their personal network to a limited set of peers, depending on the level of trust with them. This means that the effective social network (used for information exchange) may be a subset of the complete social network, and may present different structural patterns, which could limit information diffusion. In this paper, we estimate the capability of DOSN to diffuse content based on trust between social peers. To have a realistic representation of a OSN friendship graph, we consider a large-scale Facebook network, from which we estimate the trust level between friends. Then, we consider only social links above a certain threshold of trust, and we analyse the potential capability of the resulting graph to spread information through several structural indices. We test four possible thresholds, coinciding with the definition of personal social circles derived from sociology and anthropology. The results show that limiting the network to “active social contacts” leads to a graph with high network connectivity, where the nodes are still well-connected to each other, thus information can potentially cover a large number of nodes with respect to the original graph. On the other hand, the coverage drops for more restrictive assumptions. Nevertheless the re-insertion of a single excluded friend for each user is sufficient to obtain good coverage (i.e., always higher than 40 %) even in the most restricted graphs. We also analyse the potential capability of the network to spread information (i.e., network spreadability), studying the properties of the social paths between any pairs of users in the graph, which represent the effective channels traversed by information. The value of contact frequency between pairs of users determines a decay of trust along the path (the higher the contact frequency the lower the decay), and a consequent decay in the level of trustworthiness of information traversing the path. We show that selecting the link to re-insert in the network with probability proportional to its level of trust is the best re-insertion strategy, as it leads to the best connectivity/spreadability combination.     

Multilayer grid embeddings for VLSI

In this paper we propose two new multilayer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes exist only on one layer, we prove a tight area × (number of contact cuts) = (n ²) tradeoff for embeddingn-node planar graphs of bounded degree in two layers. For the second model in which nodes exist simultaneously on all layers, we give a number of upper bounds on the area needed to embed groups using no contact cuts. We show that anyn-node graph of thickness 2 can be embedded on two layers inO(n ²) area. This bound is tight even if more layers and any number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers inO(n ^3/2(logn)²) area.Some of our embedding algorithms have the additional property that they can respect prespecified grid placements of the nodes of the graph to be embedded. We give an algorithm for embeddingn-node graphs of thicknessk ink layers usingO(n ³) area, using no contact cuts, and respecting prespecified node placements. This area is asymptotically optimal for placement-respecting algorithms, even if more layers are allowed, as long as a fixed fraction of the edges do not use contact cuts. Our results use a new result on embedding graphs in a single-layer grid, namely an embedding ofn-node planar graphs such that each edge makes at most four turns, and all nodes are embedded on the same line.The first author's research was partially supported by NSF Grant No. MCS 820-5167.     

Synthesis of dependency-aware traffic generators from NoC simulation traces

Networks-on-chip (NoCs) are currently the most appropriate communication infrastructure for many-core embedded systems. As NoCs become a de facto standard for on-chip systems, traffic generation models become critical for system-on-chip (SoC) design. Traditional trace-based traffic distorts the injection rate and the effects of congestion due to the lack of packets dependency information. They also have large data storage requirements. In this paper, we propose a new framework to process traces generated by message passing applications modeled as acyclic task graphs. This framework builds dependency-aware traffic generators (DATGs) by retrieving the packet dependencies from traces in a single simulation. The DATGs accurately replace the application nodes in emulations or simulations to explore the NoC design space. Our experimental analysis showed that our framework is more accurate than trace-based simulation for a broad range of NoC configurations. Moreover, our proposed framework uses only 3% of the data storage required by the traces.     

A regular scalable fault tolerant interconnection network for distributed processing

Bounded degree networks like deBruijn graphs or wrapped butterfly networks are very important from VLSI implementation point of view as well as for applications where the computing nodes in the interconnection networks can have only a fixed number of I/O ports. One basic drawback of these networks is that they cannot provide a desired level of fault tolerance because of the bounded degree of the nodes. On the other hand, networks like hypercube (where degree of a node grows with the size of a network) can provide the desired fault tolerance but the design of a node becomes problematic for large networks. In their attempt to combine the best of the both worlds, authors in [IEEE Transactions on Parallel and Distributed Systems 4(9) (1993) 962] proposed hyper-deBruijn (HD) networks that have many additional features of logarithmic diameter, partitionability, embedding, etc. But, HD networks are not regular, are not optimally fault tolerant and the optimal routing is relatively complex. Our purpose in the present paper is to extend the concepts used in the above-mentioned reference to propose a new family of scalable network graphs that retain all the good features of HD networks and at the same time are regular and maximally fault tolerant; the optimal point to point routing algorithm is significantly simpler than that of the HD networks. We have developed some new interesting results on wrapped butterfly networks in the process.     

Annotation processes for flexible management of contextual information

We propose the use of annotations as a way to flexibly enrich a domain of interest with information concerning different contexts of use for its elements. We provide a formal model of annotation in the framework of typed graphs, in which the presence of annotations is reified through nodes and edges of specific types, relating nodes from different domains. This allows the flexible activation and de-activation of annotations, as well as the addition of several annotations from different domains on the same element. We show that annotations give rise to a category, where pushouts are the basic construct for the composition of annotation-related processes. We prove some properties of annotated graphs and discuss examples drawn from several fields.     

SmartTouch: electric skin to touch the untouchable

Augmented haptics lets users touch surface information of any modality. SmartTouch uses optical sensors to gather information and electrical stimulation to translate it into tactile display. Augmented reality is an engineer's approach to this dream. In AR, sensors capture artificial information from the world, and existing sensing channels display it. Hence, we virtually acquire the sensor's physical ability as our own. Augmented haptics, the result of applying AR to haptics, would allow a person to touch the untouchable. Our system, SmartTouch, uses a tactile display and a sensor. When the sensor contacts an object, an electrical stimulation translates the acquired information into a tactile sensation, such as a vibration or pressure, through the tactile display. Thus, an individual not only makes physical contact with an object, but also touches the surface information of any modality, even those that are typically untouchable.     

A Port Graph Calculus for Autonomic Computing and Invariant Verification

From our previous work on biochemical applications, the structure of port graph (or multigraph with ports) and a rewriting calculus have proved to be well-suited formalisms for modeling interactions between proteins. Then port graphs have been proposed as a formal model for distributed resources and grid infrastructures, where each resource is modeled by a node with ports. The lack of global information and the autonomous and distributed behavior of components are modeled by a multiset of port graphs and rewrite rules which are applied locally, concurrently, and non-deterministically. Some computations take place wherever it is possible and in parallel, while others may be controlled by strategies. In this paper, we first introduce port graphs as graphs with multiple edges and loops, with nodes having explicit connection points, called ports, and edges attaching to ports of nodes. We then define an abstract biochemical calculus that instantiates to a rewrite calculus on these graphs. Rules and strategies are themselves port graphs, i.e. first-class objects of the calculus. As a consequence, they can be rewritten as well, and rules can create new rules, providing a way of modeling adaptive systems. This approach also provides a formal framework to reason about computations and to verify useful properties. We show how structural properties of a modeled system can be expressed as strategies and checked for satisfiability at each step of the computation. This provides a way to ensure invariant properties of a system. This work is a contribution to the formal specification and verification of adaptive systems and to theoretical foundations of autonomic computing.     

Distributed minimum dominating set approximations in restricted families of graphs

A dominating set is a subset of the nodes of a graph such that all nodes are in the set or adjacent to a node in the set. A minimum dominating set approximation is a dominating set that is not much larger than a dominating set with the fewest possible number of nodes. This article summarizes the state-of-the-art with respect to finding minimum dominating set approximations in distributed systems, where each node locally executes a protocol on its own, communicating with its neighbors in order to achieve a solution with good global properties. Moreover, we present a number of recent results for specific families of graphs in detail. A unit disk graph is given by an embedding of the nodes in the Euclidean plane, where two nodes are joined by an edge exactly if they are in distance at most one. For this family of graphs, we prove an asymptotically tight lower bound on the trade-off between time complexity and approximation ratio of deterministic algorithms. Next, we consider graphs of small arboricity, whose edge sets can be decomposed into a small number of forests. We give two algorithms, a randomized one excelling in its approximation ratio and a uniform deterministic one which is faster and simpler. Finally, we show that in planar graphs, which can be drawn in the Euclidean plane without intersecting edges, a constant approximation factor can be ensured within a constant number of communication rounds.