Complex networks, data mining, causality, and beyond

Over the last few weeks Innaxis has published two papers that may be of interest to air transport researchers, among others.

The first paper is an extensive review on the combined use of complex network theory and data mining. Not only do complex network analysis and data mining share the same goal in general- that of extracting information from complex systems to ultimately create a new compact quantifiable representation- but they also often address similar problems as well. Despite these commonalities, a surprisingly low number of researchers take advantage of methodologies, as many conclude that these two fields are either largely redundant or totally antithetic. In this review, we challenge this perception, show how this state of affairs should be relegated to contingent rather than conceptual differences, and that these two fields can in fact advantageously be used in a synergistic manner. The review starts by presenting an overview of both fields, and by illustrating some of their fundamental concepts. A variety of contexts in which complex network theory and data mining have been used in a synergistic manner are then presented. Finally, all discussed concepts are illustrated with worked examples through a series of hands-on sections, which we hope will help the reader to put these ideas in practice. If you ever wonder how a real-world problem can be tackled by these two techniques, you should definitively read this review!

 

 

The second paper addresses the common misinterpretation of correlation vs causality. Following this idea, many causality metrics have been proposed in the literature, all sharing a same drawback: they are defined for time series. In other words, the system (or systems) under analysis should display a time evolution. Associating causality to the temporal domain is intuitive, due to the way the human brain incorporates time into our perception of causality; nevertheless, such association results in some rather important problems.

For instance, suppose one is trying to detect if there is a causality relation between the workload of an ATC controller and the appearance of loss of separation events. These events are only defined at one point in time. To illustrate, one can detect an instance of a loss of separation and check the corresponding workload; afterwards, perform the same actions for another event; and so forth. In the end, the researcher would get two vectors of features, which do not encode any temporal evolutions – in other words, consecutive values are not correlated. So, in this situation, how can we detect if a true causality (and not just a correlation) is present?

In this paper we propose a novel metric able to detect causality within static data sets, by analysing how extreme events in one element correspond to the appearance of extreme events in a second element- refer to the picture above for a graphical representation. The metric is able to detect non-linear causalities, to analyse both cross-sectional and longitudinal data sets, and to discriminate between real causalities and correlations caused by confounding factors.

If you are interested in these ideas, feel free to have a look at these two papers:

M. Zanin et al., Combining complex networks and data mining: why and how. Physics Reports (2016), pp. 1-44. http://authors.elsevier.com/a/1T3yF_8QfbYE-k. Also available at: http://arxiv.org/abs/1604.08816
M. Zanin, On causality of extreme events. PeerJ. Also available at: http://arxiv.org/abs/1601.07054

If you have questions about them, please contact M. Zanin at mzanin@innaxis.org

Finally, Seddik Belkoura is going to present a paper at the forthcoming ICRAT 2016, Philadelphia, about the use of the static causality metric to study delay propagation. You can find the paper on the official website of the conference (http://www.icrat.org/), and also by contacting him at sb@innaxis.org.

Guardar

Innaxis farthest east: CHINA! 1st EU-US-Chinese symposium on CS in Air Transport

Between April 10 to 12, our Principal Researcher Massimiliano Zanin made a long trip. The objective: co-organise the first Chinese / EU / USA Symposium on Complexity Science in Air Transportation, which took place in the Beihang University, Beijing.

The event has been a success, including invited keynotes of leading researchers like Shlomo Havlin, of the Bar-Ilan University, and Mark Hansen of UC Berkeley. Noteworthy has also been the participation of the ComplexWorld network, through Andrew Cook (University of Westminster) and Fabrizio Lillo (Scuola Normale Superiore di Pisa).

As for Massimiliano, he presented an unconventional idea in his talk “The air transport vs. the human brain: two worlds apart?”: the human brain and the air transport are two systems not at all different, which can (and ought to) be studied using the same techniques drawn from statistical physics. By considering the air transport as an information processing system, the strategies used in neuroscience can seamlessly be adapted, in order to improve our knowledge of processes like delay propagations. This idea has been illustrated using several examples, drawn from some research works done in collaboration with Seddik Belkoura and Andrew Cook in the past two years.

 

 

More information about the event is available at: http://airnets.de/Symposium2016/index.html

Additionally, if reading Chinese is not a problem for you, you may be interested in the press release in the Beihang University website: http://news.buaa.edu.cn/zhxw/95477.htm

Secure information sharing – secure multi-party computation in air traffic management

Easing confidentiality between business rivals through a clever use of mathematics

Secure Multi-party Computation is the preferred technique when multiple parties have to perform a computation, yet do not want to share private, confidential data. SecureDataCloud, the first research project about the application of SMC in air transport, has been recently completed by a team led by Dr. Zanin. The foundations of this technique are valuable for potential applications in the context of cyber-security, air transport and other domains.

The history of cryptography, i.e. the study of techniques for secure communication in the presence of adversaries, is fascinating and has been linked to social and cultural changes. Over two thousand years ago, the Caesar cypher was the state of the art. It involved an alphabet shift with a constant key, such that “abc” may be encrypted to “bcd”. This concept, while in actuality very simple to understand in present day, was a novel technique in the days of the Roman Empire.

Then, a substantial change in technology occurred in 1553, when the Vigenère cipher was invented by Giovan Battista Bellaso. This new cypher relied on a large key word, which controls the letter substitution depending on the letter used from the key word. If the key word is long enough, ideally, as long as the message itself, this schema is secure. The challenge of transmitting a long secret key was to use sentences from books that were owned by both the sender and the receiver, which in those days was less probable.

The most progress made in the cryptographic evolution has been achieved in the last decades, through the development of Secure Multi-party Computation (SMC) techniques. Previously, the scenario involved two parties trying to maintain privacy against an external adversary. However, in many modern applications, two or more parties need to maintain their privacy against each other, not just external adversaries. Yes, they still need to collaborate to exchange critical information, which is a significant change in the information security framework.

Secure computation was invented by Andrew Yao in 1982, and can be exemplified by the following problem, as originally proposed by Yao himself. Suppose two millionaires, Alice and Bob, are interested in knowing which is wealthier yet they do not want to reveal their actual wealth. To put in a different way, both parties (Alice and Bob) possess some information, respectively represented by A and B; the SMC problem is then an evaluation of a function C = f(A, B), such that at the end both Alice and Bob get to know C, but they don’t gain any additional information about A and B.

Many solutions have been proposed in the last 30 years enabling the evaluation of (almost any) functions. The mathematics involved in such computations could be complex and the computational cost associated with SMC protocols is high. Just to give an example, the secure two-party evaluation of an Advanced Encryption Standard (AES) encryption was achieved in 2007 (Lindell and Pinkas, 2007) but the computation takes around 20 minutes. Using SMC to access your bank account could be really secure but access to the information may take 20 minutes.

Innaxis started working on solving certain information-sharing paradigms in Air Traffic Management (ATM) using SMC in 2012. In these scenarios, different stakeholders must share information to reach a common goal, as mandated by the concept of Collaborative Decision-Making (CDM). Such information may be confidential and parties may not be comfortable sharing them due to high risk and confidentiality. For instance, considering the case of slot trading, airlines may be interested in trading slots, but revealing their target price is tantamount to giving away business information (i.e. the business value of that slot, the number of passengers they expect to allocate there, and so forth). Other applications of SMC could enable the exchange of safety information; exchanging the number of certain safety critical events might be beneficial to all airlines, but this kind of information is confidential and very sensitive and would better be shared through a SMC protocol.

Can these problems be solved by a trusted “neutral-party”, which is in charge of managing the information and ensure no ill-conceived analyses are executed? Possibly, but you have to find and trust the information maintains confidentiality within the neutral-party and ensure the security of the communication links in the transmission of the data. Additionally, having a single entity with access to every piece of data makes the system very vulnerable to cyber-attacks.

Starting from these considerations, we decided to start a research line concerning the use of SMC within air transport. The SESAR programme of the European Union recognised the value of this and financed the research project SecureDataCloud. We addressed two important problems: the trading of airport slots by airlines, and the calculation of delay statistics, both processed in a secure way.

The reader may refer to the several publications that resulted from this research work, with concrete implementation details that take address and solve the mathematical and computation challenges. Specifically, (Zanin et al., 2013) outlines the main ideas beyond the project and how SMC could be applied to ATM. (Zanin et al., 2014) and (Zanin et al., 2016) study a parallel problem, i.e. the creation of a secure CO2 allowance trading mechanism. Finally, (Zanin et al., 2015) deals with the problem of creating a secure trading mechanism for airport slot allocation.

Massimiliano Zanin will present SMC for air transport applications in the forthcoming Eurocontrol Cyber-security workshop, next March 23rd in Toulouse. If you need more details, about this talk or SMC in general, please feel free to contact Massimiliano, at mz@innaxis.org.

 

References:

Y. Lindell and B. Pinkas, “An efficient protocol for secure two-party computation in the presence of malicious adversaries,”Eurocrypt 2007, vol. Springer LNCS 4515, pp. 52-78, 2007.

Zanin, Massimiliano, et al. “SecureDataCloud: Introducing Secure Computation in ATM.” SESAR Innovation Days,Stockholm (2013).

Zanin, Massimiliano, et al. “Enabling the Aviation CO2 Allowance Trading Through Secure Market Mechanisms.” SESAR Innovation Days, Madrid (2014).

Zanin, Massimiliano, et al. “Design and Implementation of a Secure Auction System for Air Transport Slots.” Services (SERVICES), 2015 IEEE World Congress on. IEEE, 2015.

Zanin, Massimiliano, et al. “Towards a Secure Trading of Aviation CO2 Allowance”. Journal of Air Transport Management, in press, 2016.

Connect with us!