Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
Publications

Publications by Luís Lopes

2011

A Parallel Algorithm for Counting Subgraphs in Complex Networks

Authors
Ribeiro, P; Silva, F; Lopes, L;

Publication
BIOMEDICAL ENGINEERING SYSTEMS AND TECHNOLOGIES

Abstract
Many natural and artificial structures can be represented as complex networks. Computing the frequency of all subgraphs of a certain size can give a very comprehensive structural characterization of these networks. This is known as the subgraph census problem, and it is also important as an intermediate step in the computation of other features of the network, such as network motifs. The subgraph census problem is computationally hard and most associated algorithms for it are sequential. Here we present several increasingly efficient parallel strategies for, culminating in a scalable and adaptive parallel algorithm. We applied our strategies to a representative set of biological networks and achieved almost linear speedups up to 128 processors, paving the way for making it possible to compute the census for bigger networks and larger subgraph sizes.

2010

PARALLEL CALCULATION OF SUBGRAPH CENSUS IN BIOLOGICAL NETWORKS

Authors
Ribeiro, P; Silva, F; Lopes, L;

Publication
BIONFORMATICS 2010: PROCEEDINGS OF THE FIRST INTERNATIONAL CONFERENCE ON BIOINFORMATICS

Abstract
Mining meaningful data from complex biological networks is a critical task in many areas of research. One important example is calculating the frequency of all subgraphs of a certain size, also known as the sub graph census problem. This can provide a very comprehensive structural characterization of a network and is also used as an intermediate step in the computation of network motifs, an important basic building block of networks, that try to bridge the gap between structure and function. The subgraph census problem is com-putationally hard and here we present several parallel strategies to solve this problem. Our initial strategies were refined towards achieving an efficient and scalable adaptive parallel algorithm. This algorithm achieves almost linear speedups up to 128 cores when applied to a representative set of biological networks from different domains and makes the calculation of census for larger subgraph sizes feasible.

1999

Di_pSystem: A Parallel Programming System for Distributed Memory Architectures

Authors
Silva, FMA; Paulino, H; Lopes, LMB;

Publication
Recent Advances in Parallel Virtual Machine and Message Passing Interface, 6th European PVM/MPI Users' Group Meeting, Barcelona, Spain, September 26-29, 1999, Proceedings

Abstract
We present the architecture of a parallel programming system, the di_pSystem. Our target machine consists of clusters of multiprocessors interconnected with very fast networks. The system aims to provide a programming style close to the shared memory programming model. This is achieved by a software layer between the programmer and the operating system that supports the communication between individual computational agents and that dynamically balances the work-load in the system. This layer effectively hides much of the complexity of programming distributed architectures from the programmer while being competitive in performance. The low-level communication in the di_pSystem is implemented using MPI as a backbone. Initial results indicate that the system is close in performance to MPI, a fact that we attribute to its ability to dynamically balance the work-load in the computations. © Springer-Verlag Berlin Heidelberg 1999.

2002

P-3: Parallel peer to peer an - Internet parallel programming environment

Authors
Oliveira, L; Lopes, L; Silva, F;

Publication
WEB ENGINEERING AND PEER TO PEER COMPUTING

Abstract
P-3 is a next-generation Internet computing platform, building upon other experiments and implementing new ideas for high-performance parallel computing in the Internet environment. This paper describes its run-time system, programming model and how it compares to current state-of-the-art systems.

2010

Efficient Parallel Subgraph Counting Using G-Tries

Authors
Pinto Ribeiro, PM; Silva, FMA; Lopes, LMB;

Publication
Proceedings of the 2010 IEEE International Conference on Cluster Computing, Heraklion, Crete, Greece, 20-24 September, 2010

Abstract
Finding and counting the occurrences of a collection of subgraphs within another larger network is a computationally hard problem, closely related to graph isomorphism. The subgraph count is by itself a very powerful characterization of a network and it is crucial for other important network measurements. G-tries are a specialized data-structure designed to store and search for subgraphs. By taking advantage of subgraph common substructure, g-tries can provide considerable speedups over previously used methods. In this paper we present a parallel algorithm based precisely on gtries that is able to efficiently find and count subgraphs. The algorithm relies on randomized receiver-initiated dynamic load balancing and is able to stop its computation at any given time, efficiently store its search position, divide what is left to compute in two halfs, and resume from where it left. We apply our algorithm to several representative real complex networks from various domains and examine its scalability. We obtain an almost linear speedup up to 128 processors, thus allowing us to reach previously unfeasible limits. We showcase the multidisciplinary potential of the algorithm by also applying it to network motif discovery. © 2010 IEEE.

1998

Distribution and Mobility with Lexical Scoping in Process Calculi

Authors
Vasconcelos, VT; Lopes, LMB; Silva, FMA;

Publication
Electr. Notes Theor. Comput. Sci.

Abstract
We propose a simple model of distribution for mobile processes, independent of the underlying calculus. Conventional processes compute within sites; inter-site computation is achieved by message sending and object migration, both obeying a lexical scope. We focus on the semantics of networks, on programming practice, and on physical realization with current technology. ©1998 Published by Elsevier Science B.V.

  • 7
  • 10