Computer scientists develop new way to study molecular networks

Jan. 24, 2013 — In biology, molecules can have multi-way interactions within cells, and until recently, computational analysis of these links has been "incomplete," according to T. M. Murali, associate professor of computer science in the College of Engineering at Virginia Tech.

His group authored an article on their new approach to address these shortcomings, titled "Reverse Engineering Molecular Hypergraphs," that received the Best Paper Award at the recent 2012 ACM Conference on Bioinformatics, Computational Biology and Biomedicine.

Intricate networks of connections among molecules control the processes that occur within cells. The "analysis of these interaction networks has relied almost entirely on graphs for modeling the information. Since a link in a graph connects at most two molecules (e.g., genes or proteins), such edges cannot accurately represent interactions among multiple molecules. These interactions occur very often within cells," the computer scientists wrote in their paper.

To overcome the limitations in the use of the graphs, Murali and his students used hypergraphs, a generalization of a graph in which an hyperedge can connect multiple molecules.

"We used hypergraphs to capture the uncertainty that is inherent in reverse engineering gene to gene networks from systems biology datasets," explained Ahsanur Rahman, the lead author on the paper. "We believe hypergraphs are powerful representations for capturing the uncertainty in a network's structure."

They developed reliable algorithms that can discover hyperedges supported by sets of networks. In ongoing research, the scientists seek to use hyperedges to suggest new experiments. By capturing uncertainty in network structure, hyperedges can directly suggest groups of genes for which further experiments may be required in order to precisely discover interaction patterns. Incorporating the data from these experiments might help to refine hyperedges and resolve the interactions among molecules, resulting in fruitful interplay and feedback between computation and experiment.

Murali, and his students Ahsanur Rahman and Christopher L. Poirel, both doctoral candidates, and David L. Badger, a software engineer in Murali's group, all of Blacksburg, Va., and all in the computer science department, used funding from the National Institutes of Health and the National Science Foundation to better understand this uncertainty in these various forms of interactions.

Murali is also the co-director of the Institute for Critical Technology and Applied Science's Center for Systems Biology of Engineered Tissues and the associate program director for the computational tissue engineering interdisciplinary graduate education program at Virginia Tech.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Virginia Tech, via EurekAlert!, a service of AAAS.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Math tree may help root out fraudsters: Applying algorithm to social networks can reveal hidden connections criminals use to commit fraud

ScienceDaily (Sep. 5, 2012) — Fraudsters beware: the more your social networks connect you and your accomplices to the crime, the easier it will be to shake you from the tree.

The Steiner tree, that is.

In an article recently published in the journal Computer Fraud and Security, University of Alberta researcher Ray Patterson and colleagues from the University of Connecticut and University of California -- Merced outlined the connection linking fraud cases and the algorithm designed by Swiss mathematician Jakob Steiner. Fraud is a problem that costs Canadians billions of dollars annually and countless hours of police investigations. Patterson says that building the algorithm into fraud investigation software may provide important strategic advantages.

The criminal path of least resistance

To quote a television gumshoe, everything's connected. Figuring out who knows who and who has access to the money is like playing a game of connect-the-dots. Patterson says that for crimes like fraud, the fewer players in the scheme, the more likely it will be accomplished. Maintaining a small group of players is also what links it to the Steiner tree. He says that by analyzing various connecting social networks -- email, Facebook or the like -- finding out the who, what and how of the crime can be boiled down to numbers.

"You're really trying to find the minimum set of connectors that connect these people to the various [network] resources," he said. "The minimum number of people required is what's most likely to be the smoking gun. You can do it with math, once you know what the networks are."

Fraud and the Steiner tree, by the numbers

In their article, Patterson and his colleagues explored how networks such as phone calls, business partnerships and family relationships are used to form essential relationships in a fraud investigation. When these same relationships are layered, a pattern of connection becomes obvious. Once unnecessary links are removed and false leads are extracted, the remaining connections are most likely the best suspects. Patterson says that finding the shortest connection between the criminals and the crime is the crux of the Steiner tree.

"All of these things that we see in life, behind them is a mathematical representation," said Patterson. "There are many, many different algorithms that we can pull off a shelf and apply to real-life problems."

A potential tool for the long arm of the law?

Patterson says that with the amount of work that could potentially go into investigating a fraud case, such as obtaining warrants for phone or email records, and identifying and interviewing potential suspects, developing a program that uses a Steiner tree algorithm may save a significant portion of investigators' time -- time that, he says, could likely be reallocated to backlog or cold case files. "If you can reduce your legwork by even 20 per cent, that has massive manpower implications. I think algorithms like this one could help you reduce your legwork a lot more than that," he said.

Although there is software that police and other law enforcement agencies can use to solve fraud, Patterson sees no evidence that those programs use a Steiner tree algorithm, something he says would bring some structure to an unstructured area. He hopes programmers and investigators will take note of the findings and make changes to their practices.

"It might take several years or many years before anyone picks it up," said Patterson. "But it's a good thing if we can point people towards what's useful."

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by University of Alberta, via EurekAlert!, a service of AAAS.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Ram D Gopal, Raymond A Patterson, Erik Rolland, Dmitry Zhdanov. Social network meets Sherlock Holmes: investigating the missing links of fraud. Computer Fraud & Security, 2012; 2012 (7): 12 DOI: 10.1016/S1361-3723(12)70074-X

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Biologists create first predictive computational model of gene networks that control development of sea-urchin embryos

ScienceDaily (Aug. 29, 2012) — As an animal develops from an embryo, its cells take diverse paths, eventually forming different body parts -- muscles, bones, heart. In order for each cell to know what to do during development, it follows a genetic blueprint, which consists of complex webs of interacting genes called gene regulatory networks.

Biologists at the California Institute of Technology (Caltech) have spent the last decade or so detailing how these gene networks control development in sea-urchin embryos. Now, for the first time, they have built a computational model of one of these networks.

This model, the scientists say, does a remarkably good job of calculating what these networks do to control the fates of different cells in the early stages of sea-urchin development -- confirming that the interactions among a few dozen genes suffice to tell an embryo how to start the development of different body parts in their respective spatial locations. The model is also a powerful tool for understanding gene regulatory networks in a way not previously possible, allowing scientists to better study the genetic bases of both development and evolution.

"We have never had the opportunity to explore the significance of these networks before," says Eric Davidson, the Norman Chandler Professor of Cell Biology at Caltech. "The results are amazing to us."

The researchers described their computer model in a paper in the Proceedings of the National Academy of Sciences that appeared as an advance online publication on August 27.

The model encompasses the gene regulatory network that controls the first 30 hours of the development of endomesoderm cells, which eventually form the embryo's gut, skeleton, muscles, and immune system. This network -- so far the most extensively analyzed developmental gene regulatory network of any animal organism -- consists of about 50 regulatory genes that turn one another on and off.

To create the model, the researchers distilled everything they knew about the network into a series of logical statements that a computer could understand. "We translated all of our biological knowledge into very simple Boolean statements," explains Isabelle Peter, a senior research fellow and the first author of the paper. In other words, the researchers represented the network as a series of if-then statements that determine whether certain genes in different cells are on or off (i.e., if gene A is on, then genes B and C will turn off).

By computing the results of each sequence hour by hour, the model determines when and where in the embryo each gene is on and off. Comparing the computed results with experiments, the researchers found that the model reproduced the data almost exactly. "It works surprisingly well," Peter says.

Some details about the network may still be uncovered, the researchers say, but the fact that the model mirrors a real embryo so well shows that biologists have indeed identified almost all of the genes that are necessary to control these particular developmental processes. The model is accurate enough that the researchers can tweak specific parts -- for example, suppress a particular gene -- and get computed results that match those of previous experiments.

Allowing biologists to do these kinds of virtual experiments is precisely how computer models can be powerful tools, Peter says. Gene regulatory networks are so complex that it is almost impossible for a person to fully understand the role of each gene without the help of a computational model, which can reveal how the networks function in unprecedented detail.

Studying gene regulatory networks with models may also offer new insights into the evolutionary origins of species. By comparing the gene regulatory networks of different species, biologists can probe how they branched off from common ancestors at the genetic level.

So far, the researchers have only modeled one gene regulatory network, but their goal is to model the networks responsible for every part of a sea-urchin embryo, to build a model that covers not just the first 30 hours of a sea urchin's life but its entire embryonic development. Now that this modeling approach has been proven effective, Davidson says, creating a complete model is just a matter of time, effort, and resources.

The title of the PNAS paper is "Predictive computation of genomic logic processing functions in embryonic development." In addition to Peter and Davidson, the other author on the PNAS paper is Emmanuel Faure, a former Caltech postdoctoral scholar who is now at the École Polytechnique in France. This work was supported by the National Institute of Child Health and Human Development.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by California Institute of Technology. The original article was written by Marcus Woo.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

I. S. Peter, E. Faure, E. H. Davidson. Predictive computation of genomic logic processing functions in embryonic development. Proceedings of the National Academy of Sciences, 2012; DOI: 10.1073/pnas.1207852109

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Search engine for social networks based on the behavior of ants

ScienceDaily (June 4, 2012) — Research at Carlos III University (Universidad Carlos III) in Madrid (Universidad Carlos III -- UC3M) is developing an algorithm, based on ants' behavior when they are searching for food, which accelerates the search for relationships among elements that are present in social networks.

One of the main technical questions in the field of social networks, whose use is becoming more and more generalized, consists in locating the chain of reference that leads from one person to another, from one node to another. The greatest challenges that are presented in this area is the enormous size of these networks and the fact that the response must be rapid, given that the final user expects results in the shortest time possible. In order to find a solution to this problem, these researchers from UC3M have developed an algorithm SoSACO, which accelerates the search for routes between two nodes that belong to a graph that represents a social network.

The way SoSACO works was inspired by behavior that has been perfected over thousands of years by one of the most disciplined insects on the planet when they search for food. In general, the algorithms used by colonies of ants imitate how they are capable of finding the path between the anthill and the source of food by secreting and following a chemical trail, called a pheromone, which is deposited on the ground.

"In this study -- the authors explain -- other scented trails are also included so that the ants can follow both the pheromone as well as the scent of the food, which allows them to find the food source much more quickly." The main results of this research, which was carried out by Jessica Rivero in UC3M's Laboratorio de Bases de Datos Avanzadas (The Advanced Data Bases Laboratory -- LABDA) as part of her doctoral thesis, are summarized in a scientific article published in the journal Applied Intelligence. "The early results show that the application of this algorithm to real social networks obtains an optimal response in a very short time (tens of milliseconds)," Jessica Rivero states.

Multiple applications

Thanks to this new search algorithm, the system can find these routes more easily, and without modifying the structure of graph (an image that uses nodes and links to represents the relationships among a set of elements). "This advance allows us to solve many problems that we find in the real world, because the scenarios in which they occur can be modeled by a graph," the researchers explain. Thus, it could be applied in many different scenarios, such as to improve locating routes in FPS systems or in on-line games, to plan deliveries for freight trucks, to know if two words are somehow related or to simply know exactly which affinities two Facebook or Twitter users, for example, have in common.

This research, which has received support from the Autonomous Community of Madrid (MA2VICMR, S2009/TIC-1542) and the Ministry of Education and Science (Ministerio de Educación y Ciencia), began as part of the SOPAT project (TSI-020110-2009-419), in response to the need to guide a hotel's clients using a natural interaction system. Jessica Rivero's doctoral thesis, which deals with this subject, is titled "Búsqueda Rápida de Caminos en Grafos de Alta Cardinalidad Estáticos y Dinámicos" ("A Quick Search for Routes in Static and Dynamic Graphs of High Cardinality"); it was directed by Francisco Javier Calle y Mª Dolores Cuadra, professors in the LABDA of the Computer Science Department, and received a grade of Apto-Cum Laude (Pass-Cum Laude).

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Universidad Carlos III de Madrid - Oficina de Información Científica, via AlphaGalileo.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Understanding complex relationships: How global properties of networks become apparent locally

ScienceDaily (June 7, 2012) — From infections spreading around the globe to the onset of an epileptic seizure in the brain: Many phenomena can be seen as the effects of network activity. Often it is vitally important to understand the properties of these networks. However, they are often too complex to be described completely. Scientists from the Bernstein Center at the University of Freiburg were now able to show how global features of complex networks can be discovered in local statistical properties -- which are much more accessible for scientific investigation. The researchers were able to benefit from the high-performance computing facilities of the Bernstein Center, which are normally used to simulate the activity of nerve cells in the brain.

In an article appearing in the scientific journal PLoS ONE, Stefano Cardanobile and colleagues describe how they analysed 200,000 networks which they generated in a computer -- using models that are employed by scientists to understand the properties of naturally occurring networks. The researchers compared the results obtained from these models with well-understood networks from the real world: the metabolism of a bacterium, the relationship of synonyms in a thesaurus, and the nervous system of a worm. Thus, they were able to assess which model networks can predict the behaviour of its real-life counterpart the best. These insights can help colleagues from other fields to choose the right model in their specific research.

Most importantly, the scientists from Freiburg could demonstrate that it is possible to draw conclusions about global properties of complex networks from local statistical data. This means that one can discover important properties of networks even if they are not completely analysed -- very often an impossible task in large systems such as human social contacts or connections in the brain. Therefore, the authors see their study to represent an important step towards a better understanding of complex networks.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Albert-Ludwigs-Universität Freiburg.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Stefano Cardanobile, Volker Pernice, Moritz Deger, Stefan Rotter. Inferring General Relations between Network Characteristics from Specific Network Ensembles. PLoS ONE, 2012; 7 (6): e37911 DOI: 10.1371/journal.pone.0037911

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Elusive capacity of networks: Calculating data network's total capacity notoriously difficult, but theorists making some headway

ScienceDaily (May 15, 2012) — In its early years, information theory -- which grew out of a landmark 1948 paper by MIT alumnus and future professor Claude Shannon -- was dominated by research on error-correcting codes: How do you encode information so as to guarantee its faithful transmission, even in the presence of the corrupting influences engineers call "noise"?

Recently, one of the most intriguing developments in information theory has been a different kind of coding, called network coding, in which the question is how to encode information in order to maximize the capacity of a network as a whole. For information theorists, it was natural to ask how these two types of coding might be combined: If you want to both minimize error and maximize capacity, which kind of coding do you apply where, and when do you do the decoding?

What makes that question particularly hard to answer is that no one knows how to calculate the data capacity of a network as a whole -- or even whether it can be calculated. Nonetheless, in the first half of a two-part paper, which was published recently in IEEE Transactions on Information Theory, MIT's Muriel Médard, California Institute of Technology's Michelle Effros and the late Ralf Koetter of the University of Technology in Munich show that in a wired network, network coding and error-correcting coding can be handled separately, without reduction in the network's capacity. In the forthcoming second half of the paper, the same researchers demonstrate some bounds on the capacities of wireless networks, which could help guide future research in both industry and academia.

A typical data network consists of an array of nodes -- which could be routers on the Internet, wireless base stations or even processing units on a single chip -- each of which can directly communicate with a handful of its neighbors. When a packet of data arrives at a node, the node inspects its addressing information and decides which of several pathways to send it along.

Calculated confusion

With network coding, on the other hand, a node scrambles together the packets it receives and sends the hybrid packets down multiple paths; at each subsequent node they're scrambled again in different ways. Counterintuitively, this can significantly increase the capacity of the network as a whole: Hybrid packets arrive at their destination along multiple paths. If one of those paths is congested, or if one of its links fails outright, the packets arriving via the other paths will probably contain enough information that the recipient can piece together the original message.

But each link between nodes could be noisy, so the information in the packets also needs to be encoded to correct for errors. "Suppose that I'm a node in a network, and I see a communication coming in, and it is corrupted by noise," says Médard, a professor of electrical engineering and computer science. "I could try to remove the noise, but by doing that, I'm in effect making a decision right now that maybe would have been better taken by someone downstream from me who might have had more observations of the same source."

On the other hand, Médard says, if a node simply forwards the data it receives without performing any error correction, it could end up squandering bandwidth. "If the node takes all the signal it has and does not whittle down his representation, then it might be using a lot of energy to transmit noise," she says. "The question is, how much of the noise do I remove, and how much do I leave in?"

In their first paper, Médard and her colleagues analyze the case in which the noise in a given link is unrelated to the signals traveling over other links, as is true of most wired networks. In that case, the researchers show, the problems of error correction and network coding can be separated without limiting the capacity of the network as a whole.

Noisy neighbors

In the second paper, the researchers tackle the case in which the noise on a given link is related to the signals on other links, as is true of most wireless networks, since the transmissions of neighboring base stations can interfere with each other. This complicates things enormously: Indeed, Médard points out, information theorists still don't know how to quantify the capacity of a simple three-node wireless network, in which two nodes relay messages to each other via a third node.

Nonetheless, Médard and her colleagues show how to calculate upper and lower bounds on the capacity of a given wireless network. While the gap between the bounds can be very large in practice, knowing the bounds could still help network operators evaluate the benefits of further research on network coding. If the observed bit rate on a real-world network is below the lower bound, the operator knows the minimum improvement that the ideal code would provide; if the observed rate is above the lower bound but below the upper, then the operator knows the maximum improvement that the ideal code might provide. If even the maximum improvement would afford only a small savings in operational expenses, the operator may decide that further research on improved coding isn't worth the money.

"The separation theorem they proved is of fundamental interest," says Raymond Yeung, a professor of information engineering and co-director of the Institute of Network Coding at the Chinese University of Hong Kong. "While the result itself is not surprising, it is somewhat unexpected that they were able to prove the result in such a general setting."

Yeung cautions, however, that while the researchers have "decomposed a very difficult problem into two," one of those problems "remains very difficult. … The bound is in terms of the solution to another problem which is difficult to solve," he says. "It is not clear how tight this bound is; that needs further research."

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Massachusetts Institute of Technology. The original article was written by Larry Hardesty, MIT News Office.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Ralf Koetter, Michelle Effros, Muriel Medard. A Theory of Network Equivalence -- Part I: Point-to-Point Channels. IEEE Transactions on Information Theory, 2011; 57 (2): 972 DOI: 10.1109/TIT.2010.2102110

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Frog calls inspire a new algorithm for wireless networks

ScienceDaily (July 17, 2012) — Males of the Japanese tree frog have learnt not to use their calls at the same time so that the females can distinguish between them. Scientists at the Polytechnic University of Catalonia have used this form of calling behaviour to create an algorithm that assigns colours to network nodes -- an operation that can be applied to developing efficient wireless networks.

How can network nodes be coloured with the least possible number of colours without two consecutive nodes being the same colour? A team of researchers at the Polytechnic University of Catalonia have found a solution to this mathematical problem with the help of some rather special colleagues: Japanese tree frogs (Hyla japonica).

These male amphibians use their calls to attract the female, who can recognise where it comes from and then locate the suitor. The problem arises when two males are too close to one another and they use their call at the same time. The females become confused and are unable to determine the location of the call. Therefore, the males have had to learn how to 'desynchronise' their calls or, in other words, not call at the same time in order for a distinction to be made.

"Since there is no system of central control organising this "desynchronisation," the mechanism may be considered as an example of natural self-organisation," explains Christian Blum. With the help of his colleague Hugo Hernández, such behaviour provided inspiration for "solving the so-called 'graph colouring problem' in an even and distributed way."

A graph is a set of connected nodes. As in the case of the frog's 'desynchronised calls', operating in a 'distributed' fashion implies that there is no other way of central control that helps to solve the problem with a global vision and all the information on the situation.

In the same way, the researchers have devised a new algorithm for assigning colours to network nodes ensuring that each pair of connected nodes is not the same colour. The end goal is to generate a valid solution that uses the least amount of colours.

Application to WiFi connections

As Blum outlines, "this type of graph colouring is the formalisation of a problem that arises in many areas of the real world, such as the optimisation of modern wireless networks with no predetermined structure using techniques for reducing losses in information packages and energy efficiency improvement."

This study falls under the field of 'swarm intelligence', a branch of artificial intelligence that aims to design intelligent systems with multiple agents. This is inspired by the collective behaviour of animal societies such as ant colonies, flocks of birds, shoals of fish and frogs, as in this case.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Plataforma SINC, via AlphaGalileo.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Hugo Hernández, Christian Blum. Distributed graph coloring: an approach based on the calling behavior of Japanese tree frogs. Swarm Intelligence, 2012; 6 (2): 117 DOI: 10.1007/s11721-012-0067-2

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Skeleton key: Diverse complex networks have similar skeletons

ScienceDaily (June 1, 2012) — Northwestern University researchers are the first to discover that very different complex networks -- ranging from global air traffic to neural networks -- share very similar backbones. By stripping each network down to its essential nodes and links, they found each network possesses a skeleton and these skeletons share common features, much like vertebrates do.

Mammals have evolved to look very different despite a common underlying structure (think of a human being and a bat), and now it appears real-world complex networks evolve in a similar way.

The researchers studied a variety of biological, technological and social networks and found that all these networks have evolved according to basic growth mechanisms. The findings could be particularly useful in understanding how something -- a disease, a rumor or information -- spreads across a network.

This surprising discovery -- that networks all have skeletons and that they are similar -- was published this week by the journal Nature Communications.

"Infectious diseases such as H1N1 and SARS spread in a similar way, and it turns out the network's skeleton played an important role in shaping the global spread," said Dirk Brockmann, senior author of the paper. "Now, with this new understanding and by looking at the skeleton, we should be able to use this knowledge in the future to predict how a new outbreak might spread."

Brockmann is associate professor of engineering sciences and applied mathematics at the McCormick School of Engineering and Applied Science and a member of the Northwestern Institute on Complex Systems (NICO).

Complex systems -- such as the Internet, Facebook, the power grid, human consciousness, even a termite colony -- generate complex behavior. A system's structure emerges locally; it is not designed or planned. Components of a network work together, interacting and influencing each other, driving the network's evolution.

For years, researchers have been trying to determine if different networks from different disciplines have hidden core structures -- backbones -- and, if so, what they look like. Extracting meaningful structural features from data is one of the most challenging tasks in network theory.

Brockmann and two of his graduate students, Christian Thiemann and first author Daniel Grady, developed a method to identify a network's hidden core structure and showed that the skeletons possess some underlying and universal features.

The networks they studied differed in size (from hundreds of nodes to thousands) and in connectivity (some were sparsely connected, others dense) but a simple and similar core skeleton was found in each one.

"The key to our approach was asking what network elements are important from each node's perspective," Brockmann said. "What links are most important to each node, and what is the consensus among nodes? Interestingly, we found that an unexpected degree of consensus exists among all nodes in a network. Nodes either agree that a link is important or they agree that it isn't. There is nearly no disagreement."

By computing this consensus -- the overall strength, or importance, of each link in the network -- the researchers were able to produce a skeleton for each network consisting of all those links that every node considers important. And these skeletons are similar across networks.

Because of this "consensus" property, the researchers' method does not have the drawbacks of other methods, which have degrees of arbitrariness in them and depend on parameters. The Northwestern approach is very robust and identifies essential hubs and links in a non-arbitrary universal way.

The Volkswagen Foundation supported the research.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Northwestern University. The original article was written by Megan Fellman.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Daniel Grady, Christian Thiemann, Dirk Brockmann. Robust classification of salient links in complex networks. Nature Communications, 2012; 3: 864 DOI: 10.1038/ncomms1847

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Sharing data links in networks of cars

ScienceDaily (July 5, 2012) — A new algorithm lets networks of Wi-Fi-connected cars, whose layout is constantly changing, share a few expensive links to the Internet.

Wi-Fi is coming to our cars. Ford Motor Co. has been equipping cars with Wi-Fi transmitters since 2010; according to an Agence France-Presse story last year, the company expects that by 2015, 80 percent of the cars it sells in North America will have Wi-Fi built in. The same article cites a host of other manufacturers worldwide that either offer Wi-Fi in some high-end vehicles or belong to standards organizations that are trying to develop recommendations for automotive Wi-Fi.

Two Wi-Fi-equipped cars sitting at a stoplight could exchange information free of charge, but if they wanted to send that information to the Internet, they'd probably have to use a paid service such as the cell network or a satellite system. At the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, taking place this month in Portugal, researchers from MIT, Georgetown University and the National University of Singapore (NUS) will present a new algorithm that would allow Wi-Fi-connected cars to share their Internet connections. "In this setting, we're assuming that Wi-Fi is cheap, but 3G is expensive," says Alejandro Cornejo, a graduate student in electrical engineering and computer science at MIT and lead author on the paper.

The general approach behind the algorithm is to aggregate data from hundreds of cars in just a small handful, which then upload it to the Internet. The problem, of course, is that the layout of a network of cars is constantly changing in unpredictable ways. Ideally, the aggregators would be those cars that come into contact with the largest number of other cars, but they can't be identified in advance.

Cornejo, Georgetown's Calvin Newport and NUS's Seth Gilbert -- all three of whom did or are doing their doctoral work in Nancy Lynch's group at MIT's Computer Science and Artificial Intelligence Laboratory -- began by considering the case in which every car in a fleet of cars will reliably come into contact with some fraction -- say, 1/x -- of the rest of the fleet in a fixed period of time. In the researchers' scheme, when two cars draw within range of each other, only one of them conveys data to the other; the selection of transmitter and receiver is random. "We flip a coin for it," Cornejo says.

Over time, however, "we bias the coin toss," Cornejo explains. "Cars that have already aggregated a lot will start 'winning' more and more, and you get this chain reaction. The more people you meet, the more likely it is that people will feed their data to you." The shift in probabilities is calculated relative to 1/x -- the fraction of the fleet that any one car will meet.

The smaller the value of x, the smaller the number of cars required to aggregate the data from the rest of the fleet. But for realistic assumptions about urban traffic patterns, Cornejo says, 1,000 cars could see their data aggregated by only about five.

Realistically, it's not a safe assumption that every car will come in contact with a consistent fraction of the others: A given car might end up collecting some other cars' data and then disappearing into a private garage. But the researchers were able to show that, if the network of cars can be envisioned as a series of dense clusters with only sparse connections between them, the algorithm will still work well.

Weirdly, however, the researchers' mathematical analysis shows that if the network is a series of dense clusters with slightly more connections between them, aggregation is impossible. "There's this paradox of connectivity where if you have these isolated clusters, which are well-connected, then we can guarantee that there will be aggregation in the clusters," Cornejo says. "But if the clusters are well connected, but they're not isolated, then we can show that it's impossible to aggregate. It's not only our algorithm that fails; you can't do it."

"In general, the ability to have cheap computers and cheap sensors means that we can generate a huge amount of data about our environment," says John Heidemann, a research professor at the University of Southern California's Information Sciences Institute. "Unfortunately, what's not cheap is communications."

Heidemann says that the real advantage of aggregation is that it enables the removal of redundancies in data collected by different sources, so that transmitting the data requires less bandwidth. Although Heidemann's research focuses on sensor networks, he suspects that networks of vehicles could partake of those advantages as well. "If you were trying to analyze vehicle traffic, there's probably 10,000 cars on the Los Angeles Freeway that know that there's a traffic jam. You don't need every one of them to tell you that," he says.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Massachusetts Institute of Technology. The original article was written by Larry Hardesty.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Skeleton key: Diverse complex networks have similar skeletons

ScienceDaily (June 1, 2012) — Northwestern University researchers are the first to discover that very different complex networks -- ranging from global air traffic to neural networks -- share very similar backbones. By stripping each network down to its essential nodes and links, they found each network possesses a skeleton and these skeletons share common features, much like vertebrates do.

Mammals have evolved to look very different despite a common underlying structure (think of a human being and a bat), and now it appears real-world complex networks evolve in a similar way.

The researchers studied a variety of biological, technological and social networks and found that all these networks have evolved according to basic growth mechanisms. The findings could be particularly useful in understanding how something -- a disease, a rumor or information -- spreads across a network.

This surprising discovery -- that networks all have skeletons and that they are similar -- was published this week by the journal Nature Communications.

"Infectious diseases such as H1N1 and SARS spread in a similar way, and it turns out the network's skeleton played an important role in shaping the global spread," said Dirk Brockmann, senior author of the paper. "Now, with this new understanding and by looking at the skeleton, we should be able to use this knowledge in the future to predict how a new outbreak might spread."

Brockmann is associate professor of engineering sciences and applied mathematics at the McCormick School of Engineering and Applied Science and a member of the Northwestern Institute on Complex Systems (NICO).

Complex systems -- such as the Internet, Facebook, the power grid, human consciousness, even a termite colony -- generate complex behavior. A system's structure emerges locally; it is not designed or planned. Components of a network work together, interacting and influencing each other, driving the network's evolution.

For years, researchers have been trying to determine if different networks from different disciplines have hidden core structures -- backbones -- and, if so, what they look like. Extracting meaningful structural features from data is one of the most challenging tasks in network theory.

Brockmann and two of his graduate students, Christian Thiemann and first author Daniel Grady, developed a method to identify a network's hidden core structure and showed that the skeletons possess some underlying and universal features.

The networks they studied differed in size (from hundreds of nodes to thousands) and in connectivity (some were sparsely connected, others dense) but a simple and similar core skeleton was found in each one.

"The key to our approach was asking what network elements are important from each node's perspective," Brockmann said. "What links are most important to each node, and what is the consensus among nodes? Interestingly, we found that an unexpected degree of consensus exists among all nodes in a network. Nodes either agree that a link is important or they agree that it isn't. There is nearly no disagreement."

By computing this consensus -- the overall strength, or importance, of each link in the network -- the researchers were able to produce a skeleton for each network consisting of all those links that every node considers important. And these skeletons are similar across networks.

Because of this "consensus" property, the researchers' method does not have the drawbacks of other methods, which have degrees of arbitrariness in them and depend on parameters. The Northwestern approach is very robust and identifies essential hubs and links in a non-arbitrary universal way.

The Volkswagen Foundation supported the research.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Northwestern University. The original article was written by Megan Fellman.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Daniel Grady, Christian Thiemann, Dirk Brockmann. Robust classification of salient links in complex networks. Nature Communications, 2012; 3: 864 DOI: 10.1038/ncomms1847

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Understanding complex relationships: How global properties of networks become apparent locally

ScienceDaily (June 7, 2012) — From infections spreading around the globe to the onset of an epileptic seizure in the brain: Many phenomena can be seen as the effects of network activity. Often it is vitally important to understand the properties of these networks. However, they are often too complex to be described completely. Scientists from the Bernstein Center at the University of Freiburg were now able to show how global features of complex networks can be discovered in local statistical properties -- which are much more accessible for scientific investigation. The researchers were able to benefit from the high-performance computing facilities of the Bernstein Center, which are normally used to simulate the activity of nerve cells in the brain.

In an article appearing in the scientific journal PLoS ONE, Stefano Cardanobile and colleagues describe how they analysed 200,000 networks which they generated in a computer -- using models that are employed by scientists to understand the properties of naturally occurring networks. The researchers compared the results obtained from these models with well-understood networks from the real world: the metabolism of a bacterium, the relationship of synonyms in a thesaurus, and the nervous system of a worm. Thus, they were able to assess which model networks can predict the behaviour of its real-life counterpart the best. These insights can help colleagues from other fields to choose the right model in their specific research.

Most importantly, the scientists from Freiburg could demonstrate that it is possible to draw conclusions about global properties of complex networks from local statistical data. This means that one can discover important properties of networks even if they are not completely analysed -- very often an impossible task in large systems such as human social contacts or connections in the brain. Therefore, the authors see their study to represent an important step towards a better understanding of complex networks.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Albert-Ludwigs-Universität Freiburg.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Stefano Cardanobile, Volker Pernice, Moritz Deger, Stefan Rotter. Inferring General Relations between Network Characteristics from Specific Network Ensembles. PLoS ONE, 2012; 7 (6): e37911 DOI: 10.1371/journal.pone.0037911

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Search engine for social networks based on the behavior of ants

ScienceDaily (June 4, 2012) — Research at Carlos III University (Universidad Carlos III) in Madrid (Universidad Carlos III -- UC3M) is developing an algorithm, based on ants' behavior when they are searching for food, which accelerates the search for relationships among elements that are present in social networks.

One of the main technical questions in the field of social networks, whose use is becoming more and more generalized, consists in locating the chain of reference that leads from one person to another, from one node to another. The greatest challenges that are presented in this area is the enormous size of these networks and the fact that the response must be rapid, given that the final user expects results in the shortest time possible. In order to find a solution to this problem, these researchers from UC3M have developed an algorithm SoSACO, which accelerates the search for routes between two nodes that belong to a graph that represents a social network.

The way SoSACO works was inspired by behavior that has been perfected over thousands of years by one of the most disciplined insects on the planet when they search for food. In general, the algorithms used by colonies of ants imitate how they are capable of finding the path between the anthill and the source of food by secreting and following a chemical trail, called a pheromone, which is deposited on the ground.

"In this study -- the authors explain -- other scented trails are also included so that the ants can follow both the pheromone as well as the scent of the food, which allows them to find the food source much more quickly." The main results of this research, which was carried out by Jessica Rivero in UC3M's Laboratorio de Bases de Datos Avanzadas (The Advanced Data Bases Laboratory -- LABDA) as part of her doctoral thesis, are summarized in a scientific article published in the journal Applied Intelligence. "The early results show that the application of this algorithm to real social networks obtains an optimal response in a very short time (tens of milliseconds)," Jessica Rivero states.

Multiple applications

Thanks to this new search algorithm, the system can find these routes more easily, and without modifying the structure of graph (an image that uses nodes and links to represents the relationships among a set of elements). "This advance allows us to solve many problems that we find in the real world, because the scenarios in which they occur can be modeled by a graph," the researchers explain. Thus, it could be applied in many different scenarios, such as to improve locating routes in FPS systems or in on-line games, to plan deliveries for freight trucks, to know if two words are somehow related or to simply know exactly which affinities two Facebook or Twitter users, for example, have in common.

This research, which has received support from the Autonomous Community of Madrid (MA2VICMR, S2009/TIC-1542) and the Ministry of Education and Science (Ministerio de Educación y Ciencia), began as part of the SOPAT project (TSI-020110-2009-419), in response to the need to guide a hotel's clients using a natural interaction system. Jessica Rivero's doctoral thesis, which deals with this subject, is titled "Búsqueda Rápida de Caminos en Grafos de Alta Cardinalidad Estáticos y Dinámicos" ("A Quick Search for Routes in Static and Dynamic Graphs of High Cardinality"); it was directed by Francisco Javier Calle y Mª Dolores Cuadra, professors in the LABDA of the Computer Science Department, and received a grade of Apto-Cum Laude (Pass-Cum Laude).

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Universidad Carlos III de Madrid - Oficina de Información Científica, via AlphaGalileo.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Sharing data links in networks of cars

ScienceDaily (July 5, 2012) — A new algorithm lets networks of Wi-Fi-connected cars, whose layout is constantly changing, share a few expensive links to the Internet.

Wi-Fi is coming to our cars. Ford Motor Co. has been equipping cars with Wi-Fi transmitters since 2010; according to an Agence France-Presse story last year, the company expects that by 2015, 80 percent of the cars it sells in North America will have Wi-Fi built in. The same article cites a host of other manufacturers worldwide that either offer Wi-Fi in some high-end vehicles or belong to standards organizations that are trying to develop recommendations for automotive Wi-Fi.

Two Wi-Fi-equipped cars sitting at a stoplight could exchange information free of charge, but if they wanted to send that information to the Internet, they'd probably have to use a paid service such as the cell network or a satellite system. At the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, taking place this month in Portugal, researchers from MIT, Georgetown University and the National University of Singapore (NUS) will present a new algorithm that would allow Wi-Fi-connected cars to share their Internet connections. "In this setting, we're assuming that Wi-Fi is cheap, but 3G is expensive," says Alejandro Cornejo, a graduate student in electrical engineering and computer science at MIT and lead author on the paper.

The general approach behind the algorithm is to aggregate data from hundreds of cars in just a small handful, which then upload it to the Internet. The problem, of course, is that the layout of a network of cars is constantly changing in unpredictable ways. Ideally, the aggregators would be those cars that come into contact with the largest number of other cars, but they can't be identified in advance.

Cornejo, Georgetown's Calvin Newport and NUS's Seth Gilbert -- all three of whom did or are doing their doctoral work in Nancy Lynch's group at MIT's Computer Science and Artificial Intelligence Laboratory -- began by considering the case in which every car in a fleet of cars will reliably come into contact with some fraction -- say, 1/x -- of the rest of the fleet in a fixed period of time. In the researchers' scheme, when two cars draw within range of each other, only one of them conveys data to the other; the selection of transmitter and receiver is random. "We flip a coin for it," Cornejo says.

Over time, however, "we bias the coin toss," Cornejo explains. "Cars that have already aggregated a lot will start 'winning' more and more, and you get this chain reaction. The more people you meet, the more likely it is that people will feed their data to you." The shift in probabilities is calculated relative to 1/x -- the fraction of the fleet that any one car will meet.

The smaller the value of x, the smaller the number of cars required to aggregate the data from the rest of the fleet. But for realistic assumptions about urban traffic patterns, Cornejo says, 1,000 cars could see their data aggregated by only about five.

Realistically, it's not a safe assumption that every car will come in contact with a consistent fraction of the others: A given car might end up collecting some other cars' data and then disappearing into a private garage. But the researchers were able to show that, if the network of cars can be envisioned as a series of dense clusters with only sparse connections between them, the algorithm will still work well.

Weirdly, however, the researchers' mathematical analysis shows that if the network is a series of dense clusters with slightly more connections between them, aggregation is impossible. "There's this paradox of connectivity where if you have these isolated clusters, which are well-connected, then we can guarantee that there will be aggregation in the clusters," Cornejo says. "But if the clusters are well connected, but they're not isolated, then we can show that it's impossible to aggregate. It's not only our algorithm that fails; you can't do it."

"In general, the ability to have cheap computers and cheap sensors means that we can generate a huge amount of data about our environment," says John Heidemann, a research professor at the University of Southern California's Information Sciences Institute. "Unfortunately, what's not cheap is communications."

Heidemann says that the real advantage of aggregation is that it enables the removal of redundancies in data collected by different sources, so that transmitting the data requires less bandwidth. Although Heidemann's research focuses on sensor networks, he suspects that networks of vehicles could partake of those advantages as well. "If you were trying to analyze vehicle traffic, there's probably 10,000 cars on the Los Angeles Freeway that know that there's a traffic jam. You don't need every one of them to tell you that," he says.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Massachusetts Institute of Technology. The original article was written by Larry Hardesty.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Efficiency of multi-hop wireless networks boosted

ScienceDaily (Apr. 19, 2012) — Multi-hop wireless networks can provide data access for large and unconventional spaces, but they have long faced significant limits on the amount of data they can transmit. Now researchers from North Carolina State University have developed a more efficient data transmission approach that can boost the amount of data the networks can transmit by 20 to 80 percent.

"Our approach increases the average amount of data that can be transmitted within the network by at least 20 percent for networks with randomly placed nodes -- and up to 80 percent if the nodes are positioned in clusters within the network," says Dr. Rudra Dutta, an associate professor of computer science at NC State and co-author of a paper on the research. The approach also makes the network more energy efficient, which can extend the lifetime of the network if the nodes are battery-powered.

Multi-hop wireless networks utilize multiple wireless nodes to provide coverage to a large area by forwarding and receiving data wirelessly between the nodes. However, these networks have "hot spots" -- places in the network where multiple wireless transmissions can interfere with each other. This limits how quickly the network can transfer data, because the nodes have to take turns transmitting data at these congested points.

Data can be transmitted at low power over short distances, which limits the degree of interference with other nodes. But this approach means that the data may have to be transmitted through many nodes before reaching its final destination. Or, data can be transmitted at high power, which means the data can be sent further and more quickly -- but the powerful transmission may interfere with transmissions from many other nodes.

Dutta and Ph.D. student Parth Pathak developed an approach called centrality-based power control to address the problem. Their approach uses an algorithm that instructs each node in the network on how much power to use for each transmission depending on its final destination.

The algorithm optimizes system efficiency by determining when a powerful transmission is worth the added signal disruption, and when less powerful transmissions are needed.

The paper, "Centrality-based power control for hot-spot mitigation in multi-hop wireless networks," is published online by the journal Computer Communications, and is in press for a print version of an upcoming issue of the journal. Pathak is lead author. The research was supported in part by the U.S. Army Research Office.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by North Carolina State University.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Parth H. Pathak, Rudra Dutta. Centrality-based power control for hot-spot mitigation in multi-hop wireless networks. Computer Communications, 2012; DOI: 10.1016/j.comcom.2012.01.023

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Elusive capacity of networks: Calculating data network's total capacity notoriously difficult, but theorists making some headway

ScienceDaily (May 15, 2012) — In its early years, information theory -- which grew out of a landmark 1948 paper by MIT alumnus and future professor Claude Shannon -- was dominated by research on error-correcting codes: How do you encode information so as to guarantee its faithful transmission, even in the presence of the corrupting influences engineers call "noise"?

Recently, one of the most intriguing developments in information theory has been a different kind of coding, called network coding, in which the question is how to encode information in order to maximize the capacity of a network as a whole. For information theorists, it was natural to ask how these two types of coding might be combined: If you want to both minimize error and maximize capacity, which kind of coding do you apply where, and when do you do the decoding?

What makes that question particularly hard to answer is that no one knows how to calculate the data capacity of a network as a whole -- or even whether it can be calculated. Nonetheless, in the first half of a two-part paper, which was published recently in IEEE Transactions on Information Theory, MIT's Muriel Médard, California Institute of Technology's Michelle Effros and the late Ralf Koetter of the University of Technology in Munich show that in a wired network, network coding and error-correcting coding can be handled separately, without reduction in the network's capacity. In the forthcoming second half of the paper, the same researchers demonstrate some bounds on the capacities of wireless networks, which could help guide future research in both industry and academia.

A typical data network consists of an array of nodes -- which could be routers on the Internet, wireless base stations or even processing units on a single chip -- each of which can directly communicate with a handful of its neighbors. When a packet of data arrives at a node, the node inspects its addressing information and decides which of several pathways to send it along.

Calculated confusion

With network coding, on the other hand, a node scrambles together the packets it receives and sends the hybrid packets down multiple paths; at each subsequent node they're scrambled again in different ways. Counterintuitively, this can significantly increase the capacity of the network as a whole: Hybrid packets arrive at their destination along multiple paths. If one of those paths is congested, or if one of its links fails outright, the packets arriving via the other paths will probably contain enough information that the recipient can piece together the original message.

But each link between nodes could be noisy, so the information in the packets also needs to be encoded to correct for errors. "Suppose that I'm a node in a network, and I see a communication coming in, and it is corrupted by noise," says Médard, a professor of electrical engineering and computer science. "I could try to remove the noise, but by doing that, I'm in effect making a decision right now that maybe would have been better taken by someone downstream from me who might have had more observations of the same source."

On the other hand, Médard says, if a node simply forwards the data it receives without performing any error correction, it could end up squandering bandwidth. "If the node takes all the signal it has and does not whittle down his representation, then it might be using a lot of energy to transmit noise," she says. "The question is, how much of the noise do I remove, and how much do I leave in?"

In their first paper, Médard and her colleagues analyze the case in which the noise in a given link is unrelated to the signals traveling over other links, as is true of most wired networks. In that case, the researchers show, the problems of error correction and network coding can be separated without limiting the capacity of the network as a whole.

Noisy neighbors

In the second paper, the researchers tackle the case in which the noise on a given link is related to the signals on other links, as is true of most wireless networks, since the transmissions of neighboring base stations can interfere with each other. This complicates things enormously: Indeed, Médard points out, information theorists still don't know how to quantify the capacity of a simple three-node wireless network, in which two nodes relay messages to each other via a third node.

Nonetheless, Médard and her colleagues show how to calculate upper and lower bounds on the capacity of a given wireless network. While the gap between the bounds can be very large in practice, knowing the bounds could still help network operators evaluate the benefits of further research on network coding. If the observed bit rate on a real-world network is below the lower bound, the operator knows the minimum improvement that the ideal code would provide; if the observed rate is above the lower bound but below the upper, then the operator knows the maximum improvement that the ideal code might provide. If even the maximum improvement would afford only a small savings in operational expenses, the operator may decide that further research on improved coding isn't worth the money.

"The separation theorem they proved is of fundamental interest," says Raymond Yeung, a professor of information engineering and co-director of the Institute of Network Coding at the Chinese University of Hong Kong. "While the result itself is not surprising, it is somewhat unexpected that they were able to prove the result in such a general setting."

Yeung cautions, however, that while the researchers have "decomposed a very difficult problem into two," one of those problems "remains very difficult. … The bound is in terms of the solution to another problem which is difficult to solve," he says. "It is not clear how tight this bound is; that needs further research."

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Massachusetts Institute of Technology. The original article was written by Larry Hardesty, MIT News Office.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Ralf Koetter, Michelle Effros, Muriel Medard. A Theory of Network Equivalence -- Part I: Point-to-Point Channels. IEEE Transactions on Information Theory, 2011; 57 (2): 972 DOI: 10.1109/TIT.2010.2102110

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here