Andreas Holzinger
email: a.holzinger@hci4all.at

Human-Computer Interaction & Knowledge Discovery (HCI-KDD): What is the benefit of bringing those two fields to work together?

Keywords: Human-Computer Interaction (HCI), Knowledge Discovery in Data (KDD), HCI-KDD, E-Science, Interdisciplinary, Intersection science

A major challenge in our networked world is the increasing amount of data, which require efficient and user-friendly solutions. A timely example is the biomedical domain: the trend towards personalized medicine has resulted in a sheer mass of the generated (-omics) data. In the life sciences domain, most data models are characterized by complexity, which makes manual analysis very time-consuming and frequently practically impossible. Computational methods may help; however, we must acknowledge that the problem-solving knowledge is located in the human mind and -not in machines. A strategic aim to find solutions for data intensive problems could lay in the combination of two areas, which bring ideal pre-conditions: Human-Computer Interaction (HCI) and Knowledge Discovery (KDD). HCI deals with questions of human perception, cognition, intelligence, decision-making and interactive techniques of visualization, so it centers mainly on supervised methods. KDD deals mainly with questions of machine intelligence and data mining, in particular with the development of scalable algorithms for finding previously unknown relationships in data, thus centers on automatic computational methods. A proverb attributed perhaps incorrectly to Albert Einstein illustrates this perfectly: "Computers are incredibly fast, accurate, but stupid. Humans are incredibly slow, inaccurate, but brilliant. Together they may be powerful beyond imagination". Consequently, a novel approach is to combine HCI & KDD in order to enhance human intelligence by computational intelligence.

Challenges in the Data Intensive Sciences

Through the continuing exponential growth of data size and complexity, along with increasing computational power and available computing technologies, the data intensive sciences gain increasing importance [START_REF] Kouzes | The changing paradigm of data-intensive computing[END_REF]. E-Science is being advanced as a new science alongside theoretical science, experimental science, and computational science, as a fundamental research paradigm [START_REF] Hey | The Future of Data-Intensive Science[END_REF]. Meanwhile, it is established as the fourth paradigm in the investigation of nature, after theory, empiricism, and computation [START_REF] Bell | Beyond the data deluge[END_REF], [START_REF] Buxton | Big data: the next Google. Interview by Duncan Graham-Rowe[END_REF].

One of the grand challenges in our networked 21 st century is the large, complex, and often weakly structured [START_REF] Holzinger | On Knowledge Discovery and Interactive Intelligent Visualization of Biomedical Data -Challenges in Human-Computer Interaction & Biomedical Informatics[END_REF], [START_REF] Holzinger | Weakly Structured Data in Health-Informatics: The Challenge for Human-Computer Interaction[END_REF], or even unstructured data [START_REF] Holzinger | Combining HCI, Natural Language Processing, and Knowledge Discovery -Potential of IBM Content Analytics as an assistive technology in the biomedical domain[END_REF]. This increasingly large amount of data requires new, efficient and user-friendly solutions for handling the data. With the growing expectations of end-users, traditional approaches for data interpretation often cannot keep pace with demand, so there is the risk of delivering unsatisfactory results. Consequently, to cope with this rising flood of data, new computational and user-centered approaches are vital.

Let us look, for example, at the life sciences: biomedical data models are characterized by significant complexity [START_REF] Holzinger | Biomedical Informatics: Computational Sciences meets Life Sciences[END_REF], [START_REF] Akil | Challenges and opportunities in mining neuroscience data[END_REF], making manual analysis by the end users often impossible [START_REF] Dugas | Medizinische Informatik und Bioinformatik[END_REF]. At the same time, experts are able to solve complicated problems almost intuitively [START_REF] Polanyi | Personal Knowledge: Towards a Post-Critical Philosophy[END_REF], often enabling medical doctors to make diagnoses with high precision, without being able to describe the exact rules or processes used during their diagnosis, analysis and problem solving [START_REF] Popper | Alles Leben ist Problemlösen[END_REF]. Human thinking is basically a matter of the "plasticity" of the elements of the nervous system, whilst our digital computers (Von-Neuman machines) do not have such "plastic" elements [START_REF] Naur | Computing versus human thinking[END_REF] and according to Peter Naur for understanding human thinking we need a different, nondigital approach, one example given by his Synapse-State theory [START_REF] Naur | The neural embodiment of mental life by the synapse-state theory[END_REF] .

Interestingly, many powerful computational tools advancing in recent years have been developed by separate communities with different philosophies: Data mining and machine learning researchers tend to believe in the power of their statistical methods to identify relevant patterns -mostly automatic, without human intervention, however, the dangers of modeling artifacts grow when end user comprehension and control are diminished [START_REF] Shneiderman | Inventing Discovery Tools: Combining Information Visualization with Data Mining[END_REF], [START_REF] Shneiderman | Inventing Discovery Tools: Combining Information Visualization with Data Mining[END_REF], [START_REF] Shneiderman | Creativity support tools[END_REF], [START_REF] Shneiderman | Creativity support tools: accelerating discovery and innovation[END_REF]. Additionally, mobile, ubiquitous computing and sensors everywhere, together with low cost storage, will accelerate this avalanche of data [START_REF] Butler | computing: Everything, everywhere[END_REF], and there will be a danger of drowning in data but starving for knowledge, as Herbert Simon pointed it out 40 years ago: "A wealth of information creates a poverty of attention and a need to allocate that attention efficiently among the overabundance of information sources that might consume it" [START_REF] Simon | Designing Organizations for an Information-Rich World[END_REF].

Consequently, it is a grand challenge to work towards enabling effective human control over powerful machine intelligence by the integration of machine learning methods and visual analytics to support human insight and decision support [START_REF] Holzinger | Interacting with Information: Challenges in Human-Computer Interaction and Information Retrieval (HCI-IR)[END_REF], the latter is still the core discipline in biomedical informatics [START_REF] Holzinger | Biomedical Informatics: Computational Sciences meets Life Sciences[END_REF].

A synergistic combination of methodologies, methods and approaches of two areas offer ideal conditions for addressing these challenges: HCI, with its emphasis on human intelligence, and KDD, dealing with computational intelligence -with the goal of supporting human intelligence with machine intelligence -to discover new, previously unknown insights within the flood of data.

The main contribution of HCI-KDD is, following the notion: "science is to test ideas, engineering is to put these ideas into business" [START_REF] Holzinger | Successful Management of Research and Development[END_REF], to enable end users to find and recognize previously unknown and potentially useful and usable information. It may be defined as the process of identifying novel, valid and potentially useful data patterns, with the goal of understanding these data patterns for decision support.

Human-Computer Interaction in a Nutshell

HCI evolved from computer science interest in input-output technologies [START_REF] Von Neumann | The Computer and the Brain[END_REF]; hence it is a relatively young discipline, with its beginnings in the period when computers just began to have input-output devices on perception and cognition in interacting with machines [START_REF] Card | The psychology of Human-Computer Interaction[END_REF]. Because of multimedia applications, the importance of HCI continues to increase [START_REF]Handbook of Human-Computer Interaction[END_REF], [START_REF] Holzinger | Learning. Cognitive Basics of Multimedia Information Systems[END_REF], [START_REF] Ebert | Human-Computer Interaction[END_REF]. Today, the main focus of HCI research is on human issues, including perception, cognition, human intelligence and interaction with any kind of information at any type of device [START_REF] Hooper | Web science and human-computer interaction: forming a mutually supportive relationship[END_REF].

A recent and perfect example of HCI research is the area of visual analytics, which has established its own scientific community [START_REF] Keim | Visual Analytics: Scope and Challenges[END_REF] and maybe had it origins in Shneiderman's visual analytics mantra ("overview first, zoom/ filter, details on demand" [START_REF] Shneiderman | The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations[END_REF]) and Keim's extended mantra ("Analyse First -Show the Important -Zoom, Filter and Analyse Further -Details on Demand" [START_REF] Keim | Visual Analytics: Scope and Challenges[END_REF], [START_REF]Mastering the Information Age: Solving Problems with Visual Analytics[END_REF]).

Keim et al. [START_REF] Keim | Visual Analytics: Scope and Challenges[END_REF] provided a formal description of the visual analytics process, following some notions of Van Wijk [START_REF] Van Wijk | The value of visualization[END_REF], which demonstrates a core research of HCI relevant to solve problems involved with complex data:

Let the input data sets be , … , whereas each set , ∈ 1, … , , consists of attributes , … , . The output of this process will be called Insight . This is either obtained directly from a set of created Visualizations , or through confirmation of stated Hypotheses as the results of the automatic analysis methods.

Formally this process can be described as a transformation : → , whereas is a concatenation of functions ∈ , , , , defined as follows: describes the basic pre-processing functionality with : → and ∈ , , , , including the data transformation functions , data cleaning functions , data selection functions , and data integration functions , which are required to make the analysis functions applicable to the data set. , ∈ , symbolizes the visualization functions, which are either functions visualizing the data : → or functions visualizing hypotheses : → . , ∈ , represents the hypothesis generating process. Important in this view is that Keim et al. distinguished Insight can be gained from visualizations ∶ → or from the hypothesis itself ∶ → . This leads to a main research question in HCI: "What is interesting?" [START_REF] Dervin | Sense-making theory and practice: an overview of user interests in knowledge seeking and use[END_REF]. [START_REF] Beale | Supporting serendipity: Using ambient intelligence to augment user exploration for data mining and Web browsing[END_REF] [START_REF] Beale | Supporting serendipity: Using ambient intelligence to augment user exploration for data mining and Web browsing[END_REF] brings it to point: Interest is an essentially human construct, a perspective on relationships between data influenced by tasks, personal preferences and experience. Interest, like beauty, is in the eye of the beholder and is strongly dependent on previous knowledge and past experience [START_REF] Holzinger | Dynamic Media in Computer Science Education; Content Complexity and Learning Performance: Is Less More?[END_REF]. For a correct semantic interpretation a computer would need to understand the context in which a term is presented; however, a comprehension of complex context is beyond computation. For this and many other reasons we cannot leave the search for knowledge to computers alone. We must be able to guide them as to what it is we are looking for and on which areas to focus their phenomenal computing power. Hence, in order for a data mining system to be generically useful to us, it must have some way in which we can indicate what is interesting, and for that to be dynamic and changeable [START_REF] Ceglar | Chapter 4: Guiding Knowledge Discovery through Interactive Data Mining[END_REF].

Another recent and relevant research route in HCI is Attention Routing, which is a new idea introduced by Chau et al. [START_REF] Chau | What to do when search fails: finding information by association[END_REF] to overcome one critical problem in visual analytics: to help end users locate good starting points for analysis. Attention is of enormous importance for human information processing and through the process of selective attention, only selected subsets of the vast collection of incoming information becomes designated for further processing [START_REF] Shiffrin | Visual Processing Capacity and Attention Control[END_REF], [START_REF] Kahneman | Attention and Effort[END_REF], [START_REF] Duncan | Selective attention and the organization of visual information[END_REF].

Based on anomaly detection [START_REF] Chandola | Anomaly Detection: A Survey[END_REF], attention routing methods quasi-channel the enduser's attention through massive data structures, e.g. network structures, towards interesting nodes or sub-graphs that do not conform to "normal" behaviour. Such abnormalities often represent new knowledge that directly leads to novel insights.

From the early beginning, HCI research was focused on the measurement of human performance, heavily borrowing from the cognitive sciences [START_REF] Holzinger | Learning performance with interactive simulations in medical education: Lessons learned from results of learning complex physiological models with the HAEMOdynamics SIMulator[END_REF], [START_REF] Holzinger | Dynamic Media in Computer Science Education; Content Complexity and Learning Performance: Is Less More?[END_REF]; today HCI-research includes a large collection of various methods [START_REF] Lazar | Research Methods in Human-Computer Interaction[END_REF], [START_REF]Research Methods for Human-Computer Interaction[END_REF], [START_REF] Nestor | Research Methods in Psychology: Investigating Human Behavior[END_REF].

Knowledge Discovery in a Nutshell

Maimon & Rokach (2010) [START_REF]Data Mining and Knowledge Discovery Handbook[END_REF] define Knowledge Discovery in Databases (KDD) as an automatic, exploratory analysis and modeling of large data repositories and the organized process of identifying valid, novel, useful and understandable patterns from large and complex data sets. Data Mining (DM) is the core of the KDD process [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF].

The term KDD actually goes back to the machine learning and Artificial Intelligence (AI) community [START_REF] Piatetsky-Shapiro | Knowledge discovery in databases: 10 years after[END_REF]. Interestingly, the first application in this area was again in medical informatics: The program Rx was the first that analyzed data from about 50,000 Stanford patients and looked for unexpected side-effects of drugs [START_REF] Blum | Studying hypotheses on a time-oriented clinical database: an overview of the RX project[END_REF]. The term really became popular with the paper by [START_REF] Fayyad | The KDD process for extracting useful knowledge from volumes of data[END_REF] [START_REF] Fayyad | The KDD process for extracting useful knowledge from volumes of data[END_REF], who described the KDD process consisting of 9 subsequent steps:

1. Learning from the application domain: includes understanding relevant previous knowledge, the goals of the application and a certain amount of domain expertise;

2. Creating a target dataset: includes selecting a dataset or focusing on a subset of variables or data samples on which discovery shall be performed; 3. Data cleansing (and preprocessing): includes removing noise or outliers, strategies for handling missing data, etc.); 4. Data reduction and projection: includes finding useful features to represent the data, dimensionality reduction, etc.;

5. Choosing the function of data mining: includes deciding the purpose and principle of the model for mining algorithms (e.g., summarization, classification, regression and clustering);

6. Choosing the data mining algorithm: includes selecting method(s) to be used for searching for patterns in the data, such as deciding which models and parameters may be appropriate (e.g., models for categorical data are different from models on vectors over reals) and matching a particular data mining method with the criteria of the KDD process;

7. Data mining: searching for patterns of interest in a representational form or a set of such representations, including classification rules or trees, regression, clustering, sequence modeling, dependency and line analysis;

8. Interpretation: includes interpreting the discovered patterns and possibly returning to any of the previous steps, as well as possible visualization of the extracted patterns, removing redundant or irrelevant patterns and translating the useful ones into terms understandable by users;

9. Using discovered knowledge: includes incorporating this knowledge into the performance of the system, taking actions based on the knowledge or documenting it and reporting it to interested parties, as well as checking for, and resolving, potential conflicts with previously believed knowledge.

The repertoire of methods in KDD is enormous, ranging from classical supervised methods, for example classification trees, pruning, inducers (ID3, C4.5, CART, CHAID, QUEST, and many others), Bayesian networks, regression frameworks (Regression Splines, Smoothing Splines, Locally weighted Regression), Support Vector Machines (Hyperplane Classifiers, Non-Separable SVM Models, etc.), Rule Induction (e.g. LEMI Algorithm), to classical unsupervised methods, including Clustering Algorithms, Distance Measures, Similarity Functions, Evaluation Criteria Measures, etc., Association Rules, Frequent Set Mining, Constraint-based Data Mining (e.g. Apriori, Max-Miner, MultipleJoins, Reorder, Direct, CAP, SPIRIT, etc.), Link Analysis (e.g. Social Network Analysis), to advanced Methods including Evolutionary Algorithms, Reinforcement Learning Methods, Neural Networks, Granular Computing & Rough Sets, Swarm Intelligence, Fuzzy Logic, Graph Entropy, topological Methods etc. etc. [START_REF]Data Mining and Knowledge Discovery Handbook[END_REF], [START_REF] Piateski | Knowledge discovery in databases[END_REF], [START_REF] Cios | Data Mining in Knowledge Discovery[END_REF], [START_REF] Liu | Feature selection for knowledge discovery and data mining[END_REF], [START_REF] Fayyad | Information visualization in data mining and knowledge discovery[END_REF]. There are sheer endless possibilities of applications to solve various problems in different areas; here only a few recent examples [START_REF] Billinger | Towards a framework based on single trial connectivity for enhancing knowledge discovery in BCI[END_REF], [START_REF] Holzinger | Computational Sensemaking on Examples of Knowledge Discovery from Neuroscience Data: Towards Enhancing Stroke Rehabilitation[END_REF], [START_REF] Holzinger | On Using Entropy for Enhancing Handwriting Preprocessing[END_REF], [START_REF] Holzinger | On Applying Approximate Entropy to ECG Signals for Knowledge Discovery on the Example of Big Sensor Data[END_REF], [START_REF] Petz | On text preprocessing for opinion mining outside of laboratory environments[END_REF], [START_REF] Petz | Opinion Mining on the Web 2.0 -Characteristics of User Generated Content and Their Impacts[END_REF]. A tool to test methods, aiming at finding the most appropriate solution for a specific problem can be found here [START_REF] Holzinger | KNODWAT: A scientific framework application for testing knowledge discovery methods for the biomedical domain[END_REF].

The novelty of combining HCI-KDD

To attack the grand challenges described above, a novel and promising approach is to combine the best of two worlds -HCI-KDD with the main goal of supporting human intelligence with machine intelligence -to discover new, previously unknown insights into data [START_REF] Holzinger | On Knowledge Discovery and Interactive Intelligent Visualization of Biomedical Data -Challenges in Human-Computer Interaction & Biomedical Informatics[END_REF].

One could now argue: Why do we need a combination of two fields, each independently large enough? One answer is that the combination enables the provision of mutual benefits for both disciplines and allows problems to be tackled when they cannot be solved with a single disciplinary view. Likewise, crossdisciplinary or inter-disciplinary views fall short: whilst cross-disciplinary approaches [START_REF] Holzinger | Successful Management of Research and Development[END_REF] are basically researching outside the scope of their component disciplines, without tight cooperation or integration from other relevant disciplines interdisciplinary approaches are a "mix of disciplines" [START_REF] Holzinger | Process Guide for Students for Interdisciplinary Work in Computer Science/Informatics[END_REF] this is not a clear sentence. Consequently, trans-disciplinary approaches tend towards a beneficial fusion of disciplines, including reaching a business impact: team members from various disciplines work together on a shared problem by the application of shared conceptual frameworks, which draw together concepts, theories and approaches from those disciplines [START_REF] Mobjörk | Consulting versus participatory transdisciplinarity: A refined classification of transdisciplinary research[END_REF], [START_REF] Wickson | Transdisciplinary research: characteristics, quandaries and quality[END_REF], [START_REF] Lawrence | Futures of Transdisciplinarity[END_REF].

Such trans-disciplinary research is carried out with the explicit intent to solve multidimensional, complex problems, particularly problems (such as those related to sustainability) that involve an interface of human and natural systems [START_REF] Wickson | Transdisciplinary research: characteristics, quandaries and quality[END_REF].

This brings us back to the proverb [66] mentioned at the end of the abstract:

Computers are incredibly fast, accurate, and stupid. Human beings are incredibly slow, inaccurate, and brilliant. Together they are powerful beyond imagination.

A strategic, synergistic and consequent combination of aspects from HCI and KDD exactly addresses this proverb.

Conclusion

Let us summarize the essence of the two fields:

Human-Computer Interaction (HCI), deals mainly with aspects of human perception, cognition, intelligence, sense-making and most of all the interaction between human and machine. Knowledge Discovery from Data (KDD), deals mainly with aspects of machine intelligence, and in particular with the development of algorithms for automatic data mining.

Both disciplines have large portions of deep, unexplored and complementary subfields. A large challenge, and a possible solution to many current problems in the data-intensive sciences, may be found at the intersection of HCI and KDD.

Consequently, a novel approach is to combine HCI & KDD [START_REF] Holzinger | On Knowledge Discovery and Interactive Intelligent Visualization of Biomedical Data -Challenges in Human-Computer Interaction & Biomedical Informatics[END_REF] in order to enhance human intelligence by computational intelligence. The main contribution of HCI-KDD is to enable end users to find and recognize previously unknown and potentially useful and usable information. It may be defined as the process of identifying novel, valid and potentially useful data patterns, with the goal of understanding these data patterns [START_REF] Funk | Case-based reasoning and knowledge discovery in medical applications with time series[END_REF].

To visualize this, let us look at Figure 1: The domain expert possesses explicit domain knowledge, and by enabling him to interactively look at data sets he may be able to identify, extract and understand useful information in order to gain new, previously unknown knowledge and insight into his data sets [START_REF] Holzinger | Computational Sensemaking on Examples of Knowledge Discovery from Neuroscience Data: Towards Enhancing Stroke Rehabilitation[END_REF].

Figure 1. We assume that "thinking" and the formation of hypotheses takes place within the human brain, enabling the interactive analysis of information properties through a synergetic combination of research on human intelligence and computational intelligence [START_REF] Holzinger | On Knowledge Discovery and Interactive Intelligent Visualization of Biomedical Data -Challenges in Human-Computer Interaction & Biomedical Informatics[END_REF].

Acknowledgements

I thank the hci4all.at team and all expert members of the task force HCI-KDD.


Andreas Holzinger
email: a.holzinger@hci4all.at

Bernhard Ofner
email: b.ofner@hci4all.at

Christof Stocker
email: c.stocker@hci4all.at

André Calero Valdez
email: calero-valdez@comm.rwth-aachen.de

Anne Kathrin Schaar
email: schaar@comm.rwth-aachen.de

Martina Ziefle
email: ziefle@comm.rwth-aachen.de

Matthias Dehmer
email: matthias.dehmer@umit.at

On Graph Entropy Measures for Knowledge Discovery from Publication Network Data

Keywords: Network Measures, Graph Entropy, structural information, graph complexity measures, structural complexity

. Those measures can be understood as graph complexity measures, which evaluate the structural complexity based on the corresponding concept. We see that it is challenging to generalize such results towards different measures as every measure captures structural information differently and, hence, leads to a different entropy value. This calls for exploring the structural interpretation of a graph measure [2] which has been a challenging problem.

Introduction and Motivation for Research

Tradition in the history of science emphasizes the role of the individual genius in scientific discovery [START_REF] Merton | The Matthew Effect in Science: The reward and communication systems of science are considered[END_REF]. However, there is an ongoing trend away from such an individual based model of scientific advance towards a networked team model [START_REF] Wuchty | The increasing dominance of teams in production of knowledge[END_REF]. Teams can bring-in greater collective knowledge; however, the most convincing factor is, that multidisciplinary teams are able to maintain an integration and appraisal of different fields, which often provides an atmosphere to foster different perspectives and opinions; and this often stimulates novel ideas and enables a fresh look on methodologies to put these ideas into business [START_REF] Holzinger | Successful Management of Research Development[END_REF]. This is mainly due to the fact that many research problems, e.g. in the life sciences, are highly complex, so that know-how from different disciplines is necessary. Cooperative work in cross-disciplinary teams is thus of increasing interest.

Consequently, mixed-node publication network graphs can be used to get insights into social structures of such research groups, but elucidating the elements of cooperation in a network graph reveals more than simple co-authorship graphs, especially as a performance metric of interdisciplinarity [START_REF] Valdez | Using mixed node publication network graphs for analyzing success in interdisciplinary teams[END_REF].

However, before we can select measures to improve communication effectiveness or interpersonal relationships, it is necessary to determine which factors contribute to the interdisciplinary success and furthermore what constitutes interdisciplinary success. Moreover, it is quite important to understand the measures in depth, i.e., what kind of structural information they detect [START_REF] Dehmer | Information processing in complex networks: Graph entropy and information functionals[END_REF], [START_REF] Dehmer | On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures[END_REF], [START_REF] Dehmer | A history of graph entropy measures[END_REF], [START_REF] Holzinger | On Applying Approximate Entropy to ECG Signals for Knowledge Discovery on the Example of Big Sensor Data[END_REF].

Methods and Materials

As in previous work [START_REF] Valdez | Using mixed node publication network graphs for analyzing success in interdisciplinary teams[END_REF] we use a mixed node graph in order to analyze publication behavior. We create a reduced mixed node public network to demonstrate the research efforts of an interdisciplinary research cluster at the RWTH Aachen University.

Typically bibliometric data is visualized using co-authorship graphs, leaving out the element of the interaction (i.e. the publication). The use of mixed node publication network graphs allows a graph to contain more information (than a co-authorship graph) and can easily be reduced to one by using an injective mapping function. This type of graph allows fast human analysis of interdisciplinarity by explicating the authors tension between his discipline and his (possibly interdisciplinary) publications. When visualized properly this graph will match the users mental model, which is important in recognition tasks [START_REF] Valdez | Mental models of menu structures in diabetes assistants[END_REF]. In our particular case we use the reduced Graph G r .

Construction of the network graph

The network graph G r is constructed equally as in previous work [START_REF] Valdez | Using mixed node publication network graphs for analyzing success in interdisciplinary teams[END_REF] with two node types. A node in this case represents either an author (A-Node) or a publication (P-Node). Nonetheless both node types (i.e. vertices) are not regarded as differently from a graph theory point of view. We define the two sets representing authors and publications as follows:

A = {a | a is author in cluster of excellence at RWTH} (1)
P = {p | p is a publication funded by the cluster written by any a ∈ A} (2)

We also define two vertex-mappings f a and f p and two sets of vertices V 1 and V 2 as follows:

f a : A → V 1 , f a (a) = v; a ∈ A ∧ v ∈ V 1 (3)
f p : P → V 2 , f p (p) = v; p ∈ P ∧ v ∈ V 2 (4) with V 1 ∩ V 2 = ∅ (5)
These function represent mappings of authors and publications to vertices, and if inverted finding the "meaning" of a vertice. We define the sets E as all edges between authors and publications, when an author has written a publication:

E = {e | e = (v 1 , v 2 ), v 1 ∈ V 1 ∧ v 2 ∈ V 2 ∧ f -1 a (v 1 ) is author of f -1 p (v 2 )} (6)
We use the graph definition for Gr for our analyses:

G r = {(V, E) | V = V 1 ∪ V 2 } (7)
This bipartite graph can be visualized using standard graph visualization tools. In order to enable analysis by a human person the graph needs be lain out visually. Graph visualization is done with both Gephi [START_REF] Salotti | Supporting the Discovery of Relevant Topological Patterns in Attributed Graphs[END_REF] and D3JS (www.d3js.org). In this case 2D-spatial mapping is performed by using force-based algorithms.

For our visualization we set the size of nodes according to their corresponding degree and applied a grayscale color scheme based on betweenness centrality (see Fig. 1). Fig. 2 shows the two different node sets. White nodes denote authors, gray nodes denote publications. Both graphs share the same layout (Force Atlas 2, linlog mode, no overlap, scaling=0.3, gravity=1) and node sizes (min=10, max=50). Nodes sizes were chosen as node degrees. Authors with more publications are bigger, as well as publications with more authors are bigger.

Using force-based algorithms has the following consequences for graph visualization:

-All nodes are attracted to the center, but repel each other.

-All nodes that are connected by an edge attract each other (i.e. an author and his publication).

This allows the following visual conclusions:

-Two A-Nodes are spatially closer if they publish together (triangle inequality).

On Graph Entropies

The open source graph visualization tool Gephi allows for several different graph analyses of network graphs. Traditionally these are used with social network graphs (i.e. co-authorship graphs). Interpretation of graph statistics must be reevaluated for mixed node graphs. Graph statistics that are of interest in regard to publication networks are: -Network Entropies have been developed to determine the structural information content of a graph [START_REF] Dehmer | On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures[END_REF], [START_REF] Dehmer | Information theory of networks[END_REF]. We have to mention that the term network entropy cannot be uniquely defined. A reason for this is that by using Shannon's entropy [START_REF] Shannon | A mathematical theory of communication[END_REF], [START_REF] Mowshowitz | Entropy and the complexity of graphs: I. an index of the relative complexity of a graph[END_REF], [START_REF] Holzinger | On using entropy for enhancing handwriting preprocessing[END_REF] the probability distribution cannot be assigned to a graph uniquely. In the scientific literature, two major classes have been reported [START_REF] Dehmer | On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures[END_REF], [START_REF] Dehmer | Information processing in complex networks: Graph entropy and information functionals[END_REF], [START_REF] Mowshowitz | Entropy and the complexity of graphs revisited[END_REF]: 1. Information-theoretic measures for graphs which are based on a graph invariant X (e.g., vertex degrees, distances etc.) and an equivalence criterion [START_REF] Mowshowitz | Entropy and the complexity of graphs: I. an index of the relative complexity of a graph[END_REF]. By starting from an arbitrary graph invariant X of a given graph and an equivalence criterion, we derive a partitioning. Thus, one can further derive a probability distribution. An example thereof is to partition the vertex degrees (abbreviated as δ(v)) of a graph into equivalence classes, i.e., those classes only contain vertices with degree i = 1, 2, ..., max δ(v), see e.g. [START_REF] Dehmer | A history of graph entropy measures[END_REF]. 2. Instead of determining partitions of elements based on a given invariant, Dehmer [START_REF] Dehmer | Information processing in complex networks: Graph entropy and information functionals[END_REF] developed an approach which is based on using so called information functionals. An information functional f is a mapping which maps sets of vertices to the positive reals. The main difference to partitionbased measures (see previous item) is that we assign probability values to every individual vertex of a graph (and not to a partition), i.e.,

p f (v i ) := f (v i ) |V | j=1 f (v j ) (8)
As the probability values depend on the functional f , we infer a family of graph entropy measures

I f (G) := - |V | i=1 p f (v i ) log p f (v i ) ( 9
)
|V | is the size of the vertex set of G. Those measures have been extensively discussed in [START_REF] Dehmer | A history of graph entropy measures[END_REF].

Evidently, those information-theoretic graph measures can be interpreted as graph complexity measures.

The Graph G r contains 796 nodes split into 323 authors and 473 publications linked by 1677 edges. Applying the Gephi graph analysis reveals the following statistics. The graph shows an average degree of 4.214 and a network diameter of 23. The average path length is 7.805 and graph density is .005. The graph only contains a single connected component.

Evaluation of the Graph by using Network Entropies

In this section, we evaluate some information-theoretic network measures (graph entropies) on the given Excellence Network. To start, we briefly characterize this network by stating some graph-theoretical measures.

We evaluated the following graph entropies:

-A partition-based graph entropy measure called topological information content based on vertex orbits due to [START_REF] Mowshowitz | Entropy and the complexity of graphs: I. an index of the relative complexity of a graph[END_REF]. -Parametric graph entropies based on a special information functional f due to Dehmer [START_REF] Dehmer | Information processing in complex networks: Graph entropy and information functionals[END_REF]. The information functional we used is

f (v i ) := ρ(G) k=1 c k |S k (v i , G)|, with c k > 0 ( 10
)
summing the product of both the size of the k-sphere (i.e. the amount of nodes in G with a distance of k from v i given as |S k (v i , G)|) and arbitrary positive correction coefficients c k for all possible k from 1 to the diameter of the graph G. The resulting graph entropies have been defined by

I f := - |V | i=1 p f (v i ) log p f (v i ) (11)
-Network entropy due to [START_REF] Solé | Information Theory of Complex Networks: On Evolution and Architectural Constraints[END_REF].

-Graph entropy based on the ER model for modeling random graphs [START_REF] Ji | Network entropy based on topology configuration and its computation to random networks[END_REF].

Method Symbol Graph Entropy Topological information content [START_REF] Mowshowitz | Entropy and the complexity of graphs: I. an index of the relative complexity of a graph[END_REF] I mowsh 9.031485 Parametric graph entropies [START_REF] Dehmer | Information processing in complex networks: Graph entropy and information functionals[END_REF] I dehm 9.6258 Network entropy due to [START_REF] Solé | Information Theory of Complex Networks: On Evolution and Architectural Constraints[END_REF] I valv 0.3095548 Graph entropy based on the ER model [START_REF] Ji | Network entropy based on topology configuration and its computation to random networks[END_REF] Iwang 15090.71 Table 1. Calculated graph entropies.

We can note that the used graph entropies evaluate the complexity of our network differently. Here we will explore this problem with in illustrative exmaple, namely by considering the measures I mowsh < I dehm . In this context, the inequality I mowsh < I dehm can be understood by the fact those entropies have been defined on different concepts.

As mentioned, I mowsh is based upon the automorphism group of a graph and, therefore, can be interpreted as a symmetry measure. This measure vanishes if all vertices are located in only one orbit. By contrast, the measure is maximal (= log 2 (|V |)) if the input graph equals the so-called identity graph; that means all vertex orbits are singleton sets. In our case, we obtain I mowsh = 9.0315 < log 2 (796) = 9.6366 and conclude that according to the definition of I mowsh , the excellence network is rather unsymmetrical.

Instead, the entropy I dehm characterizes the diversity of the vertices in terms of their neighborhood, see [START_REF] Dehmer | On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures[END_REF]. The higher the value of I dehm , the less topologically different vertices are in the graph and, finally, the higher is the inner symmetry of our excellence network. Again, maximum entropy for our network equals log 2 (796) = 9.6366. Based on the fact that for the complete graph K, I dehm (K n ) = log(n) holds, we conclude from the result I dehm = 9.6258 that the excellence network is highly symmetrical and connected and could theoretically be obtained by deleting edges from K 796 .

The interpretation of the results for I valv and I wang can be done similarly by arguing based on their definitions.

Discussion

Different entropy measure deliver different results because they are based on different graph properties. When using the aforementioned entropy measures in a mixed-node publication graph measures of symmetry I dehm (based on vertex neighborhood diversity) or I mowsh (based on the graph automorphism) deliver different measures of entropy. Interpreted we could say, that authors/publications are similar in regard to their neighborhoods (i.e. authors show similar publication behavior, publications show similar author structures) but the whole graph shows low measures of automorphism-based symmetry to itself. This could mean authors or publications can not be exchanged for one another without changing basic properties of the graph. But since authors and publications are used in the same vertex set there are also implications of interpretation between these sets. For example a graph isomorphisms that maps vertices from V 1 to V 2 should not be included in the measure, because they are not intelligible from an interpretation point of view. New measures of entropy specialized for mixed-node graphs are required to accurately measure graph properties in such graphs.

Conclusion

In this paper, we evaluated information-theoretic network measures on publication networks. In our case, we used the excellence network from the RWTH Aachen, described in [START_REF] Valdez | Using mixed node publication network graphs for analyzing success in interdisciplinary teams[END_REF]. Those measures can be understood as graph complexity measures which evaluate the structural complexity based on the corresponding concept.

A possible useful interpretation of these measures could be applied in understanding differences in subgraphs of a cluster. For example one could apply community detection algorithms and compare entropy measures of such detected communities. Relating these data to social measures (e.g. balanced score card data) of sub-communities could be used as indicators of collaboration success or lack thereof, as proposed in [START_REF] Jooss | Scientific cooperation engineering in the cluster of excellence integrative production technology for high-wage countries at rwth aachen university[END_REF] and [START_REF] Schaar | Publication network visualisation as an approach for interdisciplinary innovation management[END_REF].

Nonetheless we see that it is challenging to generalize such results towards different measures as every measure captures structural information differently and, hence, leads to a different entropy value. This calls for exploring the structural interpretation of a graph measure [START_REF] Dehmer | Information theory of networks[END_REF] which has been a challenging problem.

Fig. 1 .

 1 Fig.1. Gr of publication data of the excellence network from the RWTH Aachen. The node size shows the node degree whereas the node color shows the betweenness centrality. Darker color means higher centrality.

Fig. 2 .

 2 Fig. 2. Gr of publication data of the excellence network from the RWTH Aachen. The node size shows the betweenness centrality. White nodes denote authors, gray nodes denote publications.

Acknowledgments. We cordially thank the Aachen House of Production for allowing us to analyze their publication data. This research was partially funded by the Excellence Initiative of the German federal and state governments.


Sourya Joyee De

Asim K Pal

Cloud-based Privacy Aware Preference Aggregation Service

Keywords: Security, privacy, preference aggregation, cloud computing, multiparty computation

Each day newer security and privacy risks are emerging in the online world. Users are often wary of using online services because they are not entirely confident of the level of security the provider is offering, particularly when such services may involve monetary transactions. Often the level of security in the algorithms underlying online and cloud-based services cannot be controlled by the user but is decided by the service provider. We propose a cloud-based Privacy Aware Preference Aggregation Service (PAPAS) that enables users to match preferences with other interested users of the service to find partners for negotiation, peer-groups with similar interests etc while also allowing users the ability to decide the level of security desired from the service, especially with respect to correct output and privacy of inputs of the protocol. It also lets users express their level of trust on the provider enabling or disabling it to act as a mediating agent in the protocols. Along with this we analyze the security of a preference hiding algorithm in the literature based on the security levels we propose for the PAPAS framework and suggest an improved version of the multi-party privacy preserving preference aggregation algorithm that does not require a mediating agent.

Introduction

The use of online services such as auctions, banking, shopping etc are everincreasing. The advent of the cloud has led to the growth of these services by giving service providers access to so-called unlimited computing power, storage and the benefits of pay-per-use. However, newer security and privacy risks are also emerging each day. Users are often wary of using online services because they are not entirely confident of the level of security the provider is offering, particularly when such services may involve monetary transactions. Online services such as auctions etc hardly provide users the choice of controlling their security requirements for the underlying algorithms. Users must solely depend on the reputation of the service provider to accept that the outcome is correct and his private inputs have not been revealed to anybody else. Intense research in secure multi-party computation in the past decades has been able to provide some solutions in this respect [START_REF] Chakraborty | Privacy preserving e-negotiation Protocols based on secure multiparty computation[END_REF][START_REF] Saroop | Multi-Attribute Auction Format for Procurement with Limited Disclosure of Buyer's Preference Structure[END_REF][START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF][START_REF] Du | A Practical Approach to Solve Secure Multi-party Computation Problems[END_REF][START_REF] Naor | Privacy Preserving Auctions and Mechanism Design[END_REF][START_REF] Cramer | A secure and Optimally Efficient Multi-Authority Election Scheme[END_REF][START_REF] Kamara | Secure Outsourced Computation in Multi-tenant Cloud[END_REF]. However, online services still do not allow users to choose their desired level of security. It may vary from user to user and the type of service being provided. In this age of rapidly growing incidents of information security breaches, providing users the ability to specify the desirable level of security can become a critical success factor for a service provider. Moreover, different users may also have different levels of trust on service providers, in our case a CSP, based on the purpose of use of such services [START_REF] De | Achieving Energy Efficiency and Security in Mobile Cloud Computing[END_REF].

In this paper we propose a privacy-aware preference aggregation service based on cloud which allows users to choose the level of security they desire from the underlying preference aggregation protocols as well as specify its level of trust for the cloud service provider, hence allowing or disallowing it to act as mediating agents in the preference aggregation protocols. Preference aggregation can be an important service before two or more persons enter into a negotiation process. Before a negotiation starts, users are interested in knowing the range of persons who share a common preference with them and with whom negotiations can be entered into. They would also like to find out the common set of alternatives in which all the negotiating parties are interested. The final interest would be to find out , the pareto-optimal subset of , which will form the basis of negotiation. Similarly, persons interested in finding friend groups or peers with similar interests can use a privacy aware preference aggregation service to do so without revealing their preferences to each other before the outcome is known. The work of [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF] has dealt with the problem of privacy preserving preference aggregation (although called preference hiding scheme in [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF]). Our work is entirely based on the protocols they suggest. The privacy-aware preference aggregation service (PAPAS) that we propose introduces the concept of allowing users to select desired level of security from the aggregation service and uses a modified version of preference hiding algorithm of [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF]. Apart from formulating the PAPAS framework, we extensively analyze the security flaws of the algorithm in [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF] under the security levels we propose in this framework and then suggest our version of the preference aggregation algorithm.

Why it is necessary to give users the freedom to choose security levels of an algorithm? Would they not simply go for the highest possible security level? If a certain protocol has to be run by the user itself, on its own device, then for him efficiency of the protocol may be a great concern, especially if he is using a resource constrained device. He will therefore make a trade-off between how efficient he wants the protocol to be and how much security is required for the purpose for which he is using the protocol. If a lower level of security satisfies his requirement, then he will hardly want to run a highly secure protocol that consumes all his resources. If the protocol is run on third-party resources (such as pay-per-use clouds), then cost will be a consideration for the user. If by choosing a lower level of security, his purpose is served then he will not want to go for a highly secure protocol that costs him much more. Therefore it has been our aim to provide users with some choice about how secure he wants the protocols to be, taking into account issues such as cost and efficiency.

2

Privacy Aware Preference Aggregation Service (PAPAS)

Let us look at some more examples to convince ourselves about the need of PAPAS. Bob is interested in buying a red Chevrolet Optra but Cathy, the car-dealer wants to sell the white variety of this car model that has been in her showroom for quite a while. Now both of them wish to know whether their preferences match and further negotiations are possible or not. But, Cathy does not want to reveal her compulsion about selling the white car because that may lead Bob to try negotiating a lower price for the car. Similarly Bob is unwilling to reveal his preference of a red car as Cathy may take advantage of his preference by demanding a higher price. Bob may even wish to search for car-dealers who have selling preferences that match his.

The movie theatre is going to play six movies , , , , and in the weekend. Alice, Melissa and Peter would like to watch a movie together but each of them has a different preference of movies. Alice's preference can be expressed as follows:

> > > > > where ' > ' indicates 'preferred over'. Similarly, Melissa's preference is: > > > > > and Peter's preference is: > > > > > . However, none of them wants to reveal his/her preference to anybody else. Now, the three friends want to find out the movies that they all can watch together such that no other choice would make any of them better off without making at least one of the others worse off. This means that finding the Pareto Optimal set of movies will solve their problem. So, if movie is preferred over movie by two of them and not by the third, then the aggregated preference says that and are incomparable. This is an all-or-nothing scenario where the overall preference is 'indifferent' or 'incomparable' if different participants have different preferences over the same alternatives and the overall preference is same as the preference of the participants when all of them have the same preference over same alternatives. After aggregation of preferences of all individuals for different pairs of alternatives, a suitable comparison rule (for e.g. the comparison algorithms in [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF]) can find out the desired Pareto-optimal set of movies.

The next example looks at the allocation of apartments to members of a cooperative housing society which has built a complex of apartments. The members can negotiate on prices. The negotiation process becomes simpler and faster if redundant options are removed through preference aggregation and obtaining the Pareto-optimal set.

For yet another example consider a builder who has a few alternative sites each having its pros and cons. There are several possibilities of constructions (amenities and apartment sizes, etc.) along with cost and time implications for each of these sites. The builder wants to find the customer preferences before he goes on to select a particular plan for a particular site. The problem becomes more complex as he does not have any fixed set of customers to talk to. This problem can possibly be reduced to some repeated applications of preference aggregation algorithm.

In both the above scenarios, a Privacy Aware Preference Aggregation Service (PAPAS) allows the user to come in contact with other users of the service with the same preferences as him/her without revealing his/her preferences to any other user or the cloud. This cloud-based service brings the advantage of being able to establish contact with other users of the service who have similar preferences but were previously unknown to this user while the cloud can execute the preference aggregation algorithms either as a mediating agent or perform multi-party computations on behalf of the participants. The second example may involve running a preference aggregation algorithm several times (for aggregating preferences for pair-wise alternatives) in which case the cloud is a potential resource provider. So participants with resource constrained devices such as smart phones can easily use PAPAS whenever they wish and wherever they are.

PAPAS compares different participants' or Decision Making Agents' (DMA) preferences of one alternative over another alternative and finds whether all of them prefer over (denoted by > ) or over (denoted by < ) or some of them prefer over and some prefer b over a (denoted by ~ ) without revealing any individual's preference to others, except what may be inferred from the output itself. We call this service 'privacy aware' because the user has the flexibility to choose the level of privacy-protection he desires from the service. A privacy aware service may protect the privacy of the user's preference from adversaries of different strengths as specified by the user. As an example, we may say that in the two illustrative scenarios above, Bob may desire a higher level of privacy of personal data than Alice as he is using the service for a purpose that may lead to a large monetary transaction as opposed to Alice's case. PAPAS enables users from different parts of the world to come in contact with each other based on their preferences in a particular context and then engage in further preference aggregation among themselves either with or without the help of the service provider as a mediating agent (MA). In this paper we have only considered 'strict' preference for the preference hiding algorithm. This may not be much meaningful if there are a large number of participants. There two possibilities, either the common set of alternatives is too small and hence of little interest, or the set is not so small, but then there will be hardly any alternative which is not in the Paretooptimal set, which also is of little consequence. In such situations we need a relaxed constraint on the 'preference' condition, e.g. majority rule. Further as already mentioned, PAPAS can also include additional services like finding intersections, comparison schemes, participants offering alternatives (with linguistic support from the service provider for uniform framing of the alternatives, for removing redundant alternatives, etc.), allowing time zone to connect people from different places, and validating the participants (through registration and authentication).

PAPAS Framework

The PAPAS framework has three layers: 1) User Interface; 2) Interpretation Middleware and 3) Operations. The first module is a user facing module that enables the user to interact with the service by allowing them to enroll in the service, specify different requirements and inputs and obtain outputs. The Interpretation Middleware interprets all forms of user specifications to enable the right choice of protocols and participants. Thirdly, the Operations layer provides the complete set of Privacy Preserving Preference Aggregation (PPA) protocols and participant choice of which only some are triggered by the Interpretation Middleware.

User Interface. The user of a preference aggregation service is concerned about the security of the preference aggregation protocol especially the privacy of his preferences. The user may also like to choose whether the cloud should participate as a mediating agent (MA) during the execution of PPA protocol depending on how much it trusts the cloud. Apart from these, the user may also like to specify an initial quality of the other participants or DMAs based on some attributes. Users interact with PAPAS through the user interface which contains the following sub-modules: 1) Enrollment; 2) Security Requirement Statement; 3) Initial Participant Requirement Statement and 4) Preference I/O (and also inputting the alternatives with linguistic support for uniform formulation of alternatives and eliminating removing alternatives).

The options for user's specifications or requirements must be simply and comprehensively expressed so that the user has no difficulty in understanding or choosing the right one. We note here that this idea is very similar to a Service Level Agreement (SLA) but is not the same. As we have already seen, PAPAS can be used for a wide range of purposes and the security and participant requirements for each use may widely vary with the particular instance of use. The user specifies its security requirements a Security Requirement Statement (SRS). Each SRS is specific to the current use of the service and is valid till the current use is over. Similarly, the user may often wish to set a quality of participants he desires for preference aggregation. For example, Bob may want to aggregate his preferences with only a well-known car dealer in city X instead of any car dealer anywhere in the world. Therefore an initial filter for participants based on certain attributes is fixed using the Initial Participant Requirement Statement. The Enrollment module enables enrollment of new users to PAPAS whereas the Preference I/O module takes the user's preference as input and provides the user with the desired output of preference aggregation. Interpretation Middleware. The specifications in the SRS are interpreted by a Security Requirements Interpretation Service (SRIS) to translate user security requirements to protocol security requirements. Protocol security requirements enables the Interpretation Middleware to trigger the right PPA protocol based on strength of adversarial model it uses. Similarly the Participant Requirements Interpretation Service (PRIS) translates participant requirements so that enrolled participants can be filtered and enrolled users satisfying the requirements can be allowed to participate in the particular user instance of a chosen PPA protocol. Protocol security requirements enables the Interpretation Middleware to trigger the right PPA protocol based on strength of adversarial model it uses. Operations. This layer consists of the most important requirements for the PAPAS framework: the complete set of PPA protocols and the choice of participants as gathered from the user by Interpretation Middleware. This layer is responsible for the execution of the triggered PPA protocol with chosen participants and communicating the outcome back to the User Interface.

2.2

The User Perspective

In this section we describe the user's view of the security requirements. Therefore we first express the adversarial models from the users' viewpoint both with respect to other participants and the CSP which may act as the mediating agent (MA) depending on user specification. Next, we specify the attributes for initial participant selection. User-specified Security Requirements for DMAs. We consider that DMAs do not deviate arbitrarily from the protocol i.e. behave maliciously in true sense of the term as used in the literature of SMC. However, they may perform certain actions that are not attributed to semi-honest behavior. When a is semi-honest, it does not deviate from the protocol and gathers information about user inputs by keeping track of intermediate steps [START_REF] Chakraborty | Privacy preserving e-negotiation Protocols based on secure multiparty computation[END_REF]. Sometimes s may collude with others or generation of fake random numbers instead of random ones when so desired by the protocol. Moreover, an adversary can corrupt s adaptively i.e. one by one as the protocol proceeds and can thus gain more information than a non-adaptive adversary. Therefore, we allow the users to base their security requirements on whether 1) s collude; 2) s generate fake random numbers instead of random numbers or 3) s are adaptively corrupted. However, we do not require the users to understand these concepts and therefore we represent the adversarial models in terms of the strength of security a user may desire. So users are only required to choose from among the three options 1) Semi-honest which indicates the lowest security level; 2) Medium Semi-honest that indicates a medium security level and 3) Strong semi-honest which indicates a strong security level. We shall indicate in a later section how these user security requirements are mapped to protocol security requirements by the SRIS component of the Interpretation Middleware. User-specified Security Requirements for Cloud (MA). The user's main concern is the privacy of his preference from other users or DMAs. However since the CSP offers PAPAS with regard to preference hiding, users impose some minimal levels of trust for the cloud. Accordingly, the user may either require the CSP to act as an MA in the PPA protocol used or require the CSP to only use such PPA protocols that do not require an MA. In the later case, the Virtual Machines (VMs) in the CSP engage in a multi-party computation without any mediating VM (referred to as VM MA) while in the former case they take the help of a VM MA. When the CSP acts as an MA, the cost to users will be much less than when several VMs engage in multi-party computation. In both cases, the user tries to protect itself from s of varied level of corruption but finally the user has to make a trade-off between his trust on the CSP as an MA and the costs involved in choosing the CSP to act as an MA and using VMs for multi-party computations.

Thus for the SRS, the user must specify two requirements on the CSP. First, whether it wishes the CSP to participate as an MA or not and second, if the CSP is required to participate as an MA then what level of trust the CSP is assigned i.e. 1) semi-trusted MA and 2) untrusted MA. We must mention here that the Interpretation Middleware is always assumed trusted in the sense that it will always interpret user requirements correctly and trigger the right protocol according to user requirements. It will not try to manipulate the user security requirements, for e.g., by setting the CSP to be semi-trusted MA when actually the user chose untrusted MA.

When the cloud is chosen to act as an MA, then all s must provide their inputs to the MA after suitable modifications and the MA after computing the aggregated preference will declare the output to the s. On the other hand, when the cloud cannot act as an MA, each is assigned a VM. The VMs, on behalf of the s, exchange messages and perform the required computations. In this scenario, each VM is assumed to have the same adversarial characteristics as the to which it is assigned. User-specified Initial Participant Requirement. The user must specify what kind of participants it wants to match its preference with on the basis of different attributes. However, the attributes will depend on the nature of use of PAPAS. If the user is using PAPAS to search for car-dealers with similar preferences then the attributes required by him to filter his initial participants will be much different from the ones he requires if he is using PAPAS for movie preference matching. Therefore, the user has to first specify the broad class of participants he is looking for. During enrollment all users are provided the option to include himself in different classes of participants based on his interest in searching and being searched for preference matching. Once this broad class is specified, the user gets options suitable to the class he specified. If he specified 'car-dealers' as his interest then the attribute options he gets are location, reputation etc of car-dealers and he must specify the required level for each of these attributes.

The Protocol Perspective

The PPA protocols used in PAPAS can tolerate one of the following adversarial behaviors: 1) there is no collusion i.e. only one acts as a non-adaptive adversary and it generates random numbers when required by the protocol (NC/R/NA); 2) a single or a group of s (i.e. collusion does not matter) is controlled by the adversary who is non-adaptive and the adversary generates numbers of its choice when actually the protocol requires random number generation (NR/NA); 3) there is collusion i.e. a group of s is controlled by the adversary who is non-adaptive and the adversary generates random numbers when required by the protocol (C/R/NA); 4) there is collusion i.e. a group of s is controlled by the adversary who is adaptive and the adversary generates random numbers when required by the protocol (C/R/A) and 5) a single or a group of s (i.e. collusion does not matter) is controlled by the adversary who is adaptive and the adversary generates numbers of its choice when actually the protocol requires random number generation (NR/A).

Privacy Preserving Preference Aggregation Protocols

Parties (persons, organizations etc) in a negotiation process want to reach a consensus without revealing their constraints on the acceptability and desirability of the available choices thus preventing unacceptable information disclosure about the business operations or strategies that they have adopted. If the information exchange essential to the negotiation process occurs through electronic media, then the process is called e-negotiation. Negotiators may also take help of support tools to arrive at a better decision or the whole process of negotiation may be fully automated [START_REF] Bichler | Towards a Structured Design of Electronic Negotiations[END_REF]. [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF] attacks the problem of finding the Pareto-optimal frontier in multi-party negotiations allowing minimum information disclosure using the solutions to secure multiparty computation problems in set theory, linear programming etc. Therefore, various privacy preserving algorithms for the different steps of solving this problem have been discussed. The steps are: 1) finding out the feasible space by using intersection algorithms and 2) finding the Pareto-optimal subset. The algorithms for the latter step consists of two major components 1) Preference Hiding Schemes and 2) Comparison Schemes. After the Comparison Scheme (that repeatedly calls the Preference Hiding Protocol), a set of non-dominated alternatives i.e. the Pareto-optimal set is arrived at. The algorithms have been designed considering that the negotiating parties i.e. the decision making agents ( s) and the mediating parties i.e. the mediating agents (MA) in the negotiation process are semi-honest. There is no extensive discussion on the effect of collusions etc on the algorithms or different possible security scenarios. We take this opportunity to use the preference hiding scheme proposed by [START_REF] Du | A Practical Approach to Solve Secure Multi-party Computation Problems[END_REF] and propose a Cloud-based Privacy Aware Preference Aggregation Service by taking into account the several possible adversary models the user may like to consider while using such a cloud-based service.

XOR-based Preference Aggregation Protocol

The XOR-based Preference hiding Algorithm proposed by [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF] is not secure under the adversarial models we have considered as there is either partial or full information disclosure (See Appendix for details). We present here a security analysis of their protocol based on the adversary models we have proposed and suggest a modification of this algorithm that will remove the drawbacks. The main motivation behind the modification is to remove the role of the central which proves to be a notorious give-away.

Before we analyze the security of the algorithm considering the adversarial models as proposed in section 2.3, we provide a brief overview of the algorithm. One of the participants i.e. s (call it the central or ) generates random representations for the preference relation > and for the preference relation < for each ( = 1 … … ) distributes these representations to the corresponding . Next each generates -1 random numbers and by using these random numbers as masks, computes ℎ =⊕ to indicate > and ℎ =⊕ to indicate < in a distributed manner. Afterwards, depending on its preference, sets the value of its preference to be either or . The earlier step using random numbers as mask is repeated to calculate in a distributed manner the aggregated preference i.e. ℎ =⊕ . We shall see that information disclosure occurs mainly because of the fact that the single , the central or , generates the random pairs of binary vectors that correspond to the choices of each . This makes powerful in terms of the information about how each 's choice is represented. Notably, the other s only know the representation of their own choices and nothing about how other s' choices are represented. For , deducing some information about the choice of at least some of the other DMAs, is not very difficult as we will show below. Also, when retains the right to generate the random representations of the preferences, it may as well calculate the values of ℎ and ℎ itself and distribute it to the other s. The only advantage of each calculating it on its own is that would not be able to manipulate this calculation somehow or give incorrect or different values for ℎ and ℎ to the s. The authors in [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF] do not clearly mention the adversary model they have considered.

We must note here that should either be elected or randomly selected at the beginning of each instance of the algorithm (although authors in [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF] do not mention this). In the whole negotiation process, the comparison of alternatives occurs a number of times and each time the preference hiding algorithm is to be used to secretly compute the overall preference of the s. We may have to either assume that an adversary controlling a fixed number of s exists before the negotiation process begins (non-adaptive) or that the adversary can select whom to corrupt as the protocol proceeds. The adversary's success lies in its ability to either begin with such a set of parties one of whom will be selected as or corrupt the party chosen as later on. If a is randomly selected to be , then beginning with a fixed set of corrupted parties does not guarantee that will belong to that set. If a is elected to the position of , then the adversary may influence the election process in such a way so that one of the colluding s gets selected as . In case of adaptive adversary, however, corrupting the central later is easier than in the non-adaptive case.

For the rest of the analysis, we consider that there are a total of s of which collude and bits are used to represent the choices of each . For results, we shall see that whenever we consider that adversaries can generate fake random num-bers without any other deviation from the protocol, full information disclosure occurs. Also since the success of the adversary depends on whether it is able to corrupt , the adaptive adversary gains a clear advantage over non-adaptive ones. Collusion helps the adversary to some extent when it is absolutely non-deviating (i.e. C/R/NA). Below we present the analysis for each adversary model. NC/R/NA. In this case, will generate the binary vectors randomly but will still be able to know some information about the choices of some of the other s. We show this by an example (see Appendix). However, will not know beforehand for which of the s it will be able to know the exact choice. This is a disadvantage for it. However, if is chosen randomly from the set of s, the chances of the adversary of corrupting becomes very low. The adversary gains no information by corrupting any other .In the worst case, full information disclosure is possible (for explanation, see Appendix). NR/NA. In this scenario, the adversary (if it is ) instead of generating random representations of preferences, can construct them in such a way so as to help it in maximizing its information gain. We see that in this scenario causing full information disclosure is very easy and it is independent of the presence of collusion. In this case also, such disclosure is possible only if the adversary is able to corrupt chances of which are very low for reasons we have already mentioned. C/R/NA. The collusion benefits only when is a part of it. A collusion of s including makes it easier for the adversary to derive information about the exact choice of at least some of the non-colluding s. So we see here that with collusion that includes , there is quite a significant information disclosure. In the worst case, full information disclosure is possible. C/R/A. This case is similar to C/R/NA with the exception that the adversary is now able to choose whom to corrupt at any point during the protocol execution which implies that it is able to corrupt almost certainly once the latter has been selected randomly. Information disclosure is same as that of C/R/NA. NR/A. This case is similar to NR/NA with the exception that the adversary is now able to choose whom to corrupt at any point during the protocol execution which implies that it is able to corrupt almost certainly once the latter has been selected randomly. This situation is definitely the worst possible scenario as it leads to full information disclosure with very high probability. The information disclosure is independent of whether there is collusion or not. Now we propose our version of the XOR-based Preference Aggregation Protocol that we use as one of the PPA protocols in PAPAS. We use the same notations as in [START_REF] Du | A Practical Approach to Solve Secure Multi-party Computation Problems[END_REF]. When more comparisons are to be made then this whole process is to be repeated. Security Analysis. The adversary can take advantage of the XOR-based algorithm by [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF] because of the use of which assumes the important role of generating the representation of the choices of each of the s. The role of has been removed in our algorithm and each is now allowed to randomly generate its own binary vector i.e. the representation of its own choice. This ensures that none of the s will have with it all the representations and hence knowing the individual choices becomes impossible even when some of them collude. No information disclosure takes place under adaptive or non-adaptive adversaries.

Our XOR-based

Conclusion and future work

In this paper we have presented a Cloud-based Privacy Aware Preference Aggregation Service that allows enrolled users to search for other unknown users of the service and find out whether preferences in a certain context match. The preference matching can occur among multiple users depending upon the use-case and the user has the flexibility to choose the security level of the protocols used to prevent privacy-breach of his preferences and the types of participants preferred for the preference aggregation. Our framework may be looked upon as a precursor to a cloud based Privacy Aware Negotiation-as-a-Service that will allow users who previously did not know each other to negotiate on their preferences to reach a consensus without revealing their preferences to anyone. Algorithms of different security level, efficiency and with different preference aggregation rules can be integrated into this service. We are working towards this end.

Existing online auction services such as eBay.com etc do provide a certain platform of negotiation between buyers and sellers but they focus on a very specific use i.e. buying and selling of goods and do not allow the flexibility to users to choose the security level of the service. In contrast, PAPAS is a highly flexible cloud-based service which allows users to choose their desired level of security and types of participants they want to interact with apart from providing a generalized arena for preference aggregation on any use-case starting from choice of movies, restaurants among friends to buying and selling of cars, real estate etc. The process of choosing security levels for algorithms must be made comprehensive for users so that users with little or no knowledge about security can effectively express their choices. Given these choices, we have ℎ =⊕ =⊕ = 00 0001 1111. Now given the values of ℎ and , we show below that it is possible for to find out the exact choices for at least some of the DMAs. The following table shows the bits (represented by X) where the representations of each of the choices of each DMA (except ) vary. Also we may consider that this table is available to .

  At the end of the algorithm, each of the s comes to know about ℎ =⊕ = ⊕Let us now tabulate the choices of the DMAs.

Table 1 .

 1 Mapping Table from User Security Requirements for of Interpretation Middleware finds out the subset of enrolled users with which a user can participate in a PPA protocol based on the attributes specified by the user. So it defines which s can participate in a particular use by a particular user of a PAPAs service.

		to Protocol Security
	Requirements for
	User Security Requirements for	Protocol Security Requirements for
	s	s

Preference Aggregation Protocol without MA

  to each DMA j where = 1, … … , ; ≠ and retains one with itself. No vector is sent to more than one . 4. Finds XOR of the vectors received in the previous step i.e. it obtains =⊕ and sends it to all other s. 5. Finds XOR of the vectors received in the previous step i.e. it obtains ℎ =⊕ . The above process is repeated for calculation of ℎ . If ℎ = ℎ then > else if ℎ = ℎ then < else ~ .

	Input: Alternatives and
	Output: > or < or ~
	Condition: No mediators
	Set up Phase: Each	generates a pair of b-bit binary vectors	,	, =
	1, … . . , . The number of bits denoted by b is fixed previously depending on the
	number of	s and is sufficiently large. This vector pair is to be kept secret by each
	.
	Calculation of ℎ and ℎ :
	The DMAs need to calculate ℎ =⊕	to indicate > and ℎ =⊕ to indicate
	< . This can be done as follows:
	Each
	1. Generates -1 random vectors , … … … ,		.
	2. Finds = ⊕ ⊕ ⊕ … … … ⊕	.
	3. Sends randomly one vector	from the set of vectors { , … … … ,	, }
	Preference Aggregation Phase:
	Each		performs the following:
	1. Finds	=	ℎ ℎ	( ) ≥ ( ) ( ) < ( )	where	,	is a random pair of bi-
	nary vectors received in the Set up phase.
	2. Generates -1 random vectors , … … … ,		.
	3. Finds = ⊕ ⊕ ⊕ … … … ⊕	.
	4. Sends randomly one vector	from the set of vectors { , … … … ,	, }
	to each	where = 1, … … , ; ≠ and retains one with itself. No
	vector is sent to more than one	.
	5. Finds XOR of the vectors received in the previous step i.e. it obtains
	=⊕	and sends it to all other	s.
	6. Finds XOR of the vectors received in the previous step i.e. it obtains
	ℎ =⊕ .
	7.

Table 3 .

 3 Choices of each DMA

			Choices
			00 1001 1011
			01 1110 1001
			10 0110 1001
			11 1111 1000
	(	)	11 0110 0101
			01 1111 1010
			00 0101 0011
			01 1100 0000
			11 0111 0001
			00 1000 0001

Table 4 .

 4 Adversary's Analysis Table

			Varying bits in Choice
			0X XX01 XXX1
			X1 1X10 1XX1
			X0 0X1X XX01
			1X 1X1X X000
	(	)	11 0110 0101
			XX 11XX 1010

Appendix

Here we present in details the security analysis of XOR-based preference hiding scheme of [START_REF] Sehgal | Finding Pareto Optimal Set of Distributed Vectors with Minimum Disclosure[END_REF] under NC/R/NA and NR/NA we propose. We have not shown the rest for lack of space. NC/R/NA. Let us suppose that there are ten DMAs among which one has been elected or randomly chosen as . Now, (say is ) generates the binary vector pair , , = 1, … . . , randomly. We assume that each vector is of 10-bit length. After randomly distributes these vector pairs to each of the s, the following is the random allocation: , and are all 0 or that of two or four of them are 1; 3) the fourth bit of three or all of , , , and DMA 9 are 1 etc. Although comes to know these pieces of information, it is difficult for it to know the exact choice of any of the other s. Since the above table can be derived only by (because only knows all the options of all the s), no other can derive these pieces of information. The worst case here will arise when the adversary generates the representations of choices such that within each pair, the choices differ by a single bit and across pairs the position of difference varies. However, since the pairs have to be randomly generated, the probability of being able to generate the representations according to the above condition will be ) where m is the number of s and b is the number of bits used in the representations of choices. We must note here that 2 >> 2 . NR/NA. In this scenario instead of generating , , = 1, … . . , randomly, the adversary (if it is ) can construct the vectors in such a way so as to help it in maximize its information disclosure. We give an example below.

Let us consider that the adversary constructs and distributes the binary vectors according to the following table :   Table 5. Vectors for Input Representation 01 0000 0000 11 0000 0000 00 1000 0000 01 1000 0000 00 0100 0000 00 1100 0000 00 0010 0000 00 0110 0000 ( ) 00 0000 0000 11 1111 1111 00 0001 0000 00 0011 0000 00 0000 1000 00 0001 1000 00 0000 0100 00 0000 1100 00 0000 0010 00 0000 0110 00 0000 0001 00 0000 0011

Let the actual choices of the DMAs be as follows:

Table 6. Choice of each DMA Choice 01 0000 0000 01 1000 0000 00 1100 0000 00 0010 0000 ( ) 00 0000 0000 00 0011 0000 00 0001 1000 00 0000 1100 00 0000 0110 00 0000 0001

Value of h

Given these choices, we have ℎ =⊕ =⊕ = 00 0100 0011. Now, as before, the adversary deduces the following table from its knowledge about the representation of the choices of each of the DMAs.

Choice

X1 0000 0000 0X 1000 0000 00 X100 0000 00 0X10 0000 ( ) 00 00X1 0000 00 0000 0000 00 000X 1000 00 0000 X100 00 0000 0X10 00 0000 00X1 Value of h Now, it becomes easy for the adversary to deduce the exact choice made by each of the other s using the property of XOR mentioned previously. So the adversary comes to know 1) the eighth bit of is 0 and its choice is . Hence prefers > ; 2) The seventh bit of must be 1 and its choice is . So it prefers < . Similarly, the adversary comes to know the choices of each of the s.