Random walk with restart over dynamic graphs

Random Walk with Restart (RWR) is an appealing measure of proximity between nodes based on graph structures. Since real graphs are often large and subject to minor changes, it is prohibitively expensive to recompute proximities from scratch. Previous methods use LU decomposition and degree reordering heuristics, entailing O(|V|^3) time and O(|V|^2) memory to compute all (|V|^2) pairs of node proximities in a static graph. In this paper, a dynamic scheme to assess RWR proximities is proposed: (1) For unit update, we characterize the changes to all-pairs proximities as the outer product of two vectors. We notice that the multiplication of an RWR matrix and its transition matrix, unlike traditional matrix multiplications, is commutative. This can greatly reduce the computation of all-pairs proximities from O(|V|^3) to O(|delta|) time for each update without loss of accuracy, where |delta| (<<|V|^2) is the number of affected proximities. (2) To avoid O(|V|^2) memory for all pairs of outputs, we also devise efficient partitioning techniques for our dynamic model, which can compute all pairs of proximities segment-wisely within O(l|V|) memory and O(|V|/l) I/O costs, where 1<=l<=|V| is a user-controlled trade-off between memory and I/O costs. (3) For bulk updates, we also devise aggregation and hashing methods, which can discard many unnecessary updates further and handle chunks of unit updates simultaneously. Our experimental results on various datasets demonstrate that our methods can be 1–2 orders of magnitude faster than other competitors while securing scalability and exactness.

Using an infra-red sensor to measure the dynamic behaviour of N2O gas escaping through different sized holes

An anastomosis is a surgical procedure that consists of the re-connection of two parts of an organ and is commonly required in cases of colorectal cancer. Approximately 80% of the patients diagnosed with this problem require surgery. The malignant tissue located on the gastrointestinal track must be resected and the most common procedure adopted is the anastomosis. Studies made with 2,980 patients that had this procedure, show that the leakage through the anastomosis was 5.1%. This paper discusses the dynamic behavior of N2O gas through different sized leakages as detected by an Infra-Red gas sensor and how the sensors response time changes depending on the leakage size. Different sized holes were made in the rigid tube to simulate an anastomostic leakage. N2O gas was injected into the tube through a pipe and the leakage rate measured by the infra-red gas sensor. Tests were also made experimentally also using a CFD (Computational Fluid Dynamics) package called FloWorks. The results will be compared and discussed in this paper.