Missing data in multiplex networks: a preliminary study
Rajesh Sharma$^{1
\IEEEauthorblockN{Rajesh Sharma\IEEEauthorrefmark{1
\IEEEauthorblockN{Rajesh Sharma$^{1
%\matteo{I tried to put immediate focus on the missing data problem. Please, check if it reads well. %Multi layer networks have recently attracted the attention of researchers from various arenas. Physicist, computer scientist and biologist all have started looking into this area. As it gives a clear and bigger picture of the real world network compared to a single layer network. A basic problem in the analysis of social networks is missing data. When a network model does not accurately capture all the actors or relationships in the social system under study, measures computed on the network and ultimately the final outcomes of the analysis can be severely distorted. For this reason, researchers in social network analysis have characterised the impact of different types of missing data on existing network measures. Recently a lot of attention has been devoted to the study of multiple-network systems, e.g., multiplex networks. In these systems missing data has an even more significant impact on the outcomes of the analyses. However, to the best of our knowledge, no study has focused on this problem yet. %as in single layer networks, the problem of missing data in multilayer is also naturally observed when the researchers collect the multi layer networks' dataset. %However, inherently because of complexity, missingness impacts the multilayer network structure property more adversely. This work is a first step in the direction of understanding the impact of missing data in multiple networks. We first discuss the main reasons for missingness in these systems, then we explore the relation between various types of missing information and their effect on network properties. We provide initial experimental evidence based on both real and synthetic data.
Conclusion.tex
%\vspace{-4pt}
\section{Conclusion and Future Work}\label{sec:concl}
%\vspace{-10pt}
Multiplex networks have been studied for a long time as they provide a more accurate representation of real world networks compared to single layer models. As in single layer networks, the problem of missing data in multiplexes is also naturally observed when the researchers collect network datasets. However, inherently because of complexity, missingness can impact multiplex network properties more adversely. In this preliminary study, we investigated the impact of missing data in multiplex networks on various network properties and provided a classification of the main causes of incompleteness. Furthermore, we performed experiments on real and synthetic datasets to understand the effect of missing data on various network properties.

\subsection{Future work}
We have a multidirectional future plan for this preliminary study:
\begin{enumerate}  
\item As an immediate next step is to perform experiments on to measure the effect of specific causes for missing data.

\item We will extend this study to perform experiments on other real datasets having a larger number of layers, with varying similarity values.
    
\item Another direction is to measure other multiplex network measures such as multidimensional betweenness centrality and multidimensional distance on different multiplex structures.

\end{enumerate}









Eval1.tex
%\vspace{-4pt}
\section{Experiments}\label{sec:eval}

\begin{figure}[ht!]
%\vspace{-20pt}
  \begin{center}
    \subfigure[Diameter]{\label{fig:BB2LDia}\includegraphics[width=0.35\textwidth]{ML-Dia4.pdf}}
    \subfigure[Cluster Coeff.]{\label{fig:BB2LCC}\includegraphics[width=0.35\textwidth]{ML-CC4.pdf}}
    \subfigure[Average Path Length]{\label{fig:BB2LApl}\includegraphics[width=0.35\textwidth]{ML-APL4.pdf}}
    %\subfigure[Diameter]{\label{fig:BB2LDia}\includegraphics[width=0.325\textwidth]{ML-Dia3.pdf}}
%    \subfigure[Cluster Coeff.]{\label{fig:BB2LCC}\includegraphics[width=0.325\textwidth]{ML-CC3.pdf}}
%    \subfigure[Average Path Length]{\label{fig:BB2LApl}\includegraphics[width=0.325\textwidth]{ML-APL3.pdf}}
  \end{center}
  %\vspace{-10pt}
  \caption{Effect of Missing Data in Multiple Layer Network.} \label{fig:MLVarySim}
  %\vspace{-2pt}
\end{figure}

%\vspace{-10pt}
% -- Impact of missing data in multiplex network measures in real world datasets on}\label{sec:eval}
%\vspace{-11pt}
Now that we know how to interpret the numerical values resulting from our experiments (layer similarity, level of missing data and precision), we can apply our methodology to real and synthetic datasets.
\subsection{Datasets}
%The real dataset does not have all the case values for the scenarios in which we were interested in evaluations. So, for a few experiments we use real dataset and for others we use synthetic dataset.
As the real and synthetic datasets have different properties, e.g., different sizes and different numbers of layers, we will use each of them to study the effect of missing data on specific properties.\\
%\subsection{Datasets}
%\vspace{-4pt}flatten network property
%\textbf{Real dataset: }
\subsubsection{Real dataset }In the network of 61 employees of a University department (both faculty and administration) the following five kinds of interactions have been recorded: i) lunch, ii) work, iii) coauthor, iv) leisure, and v) Facebook. Thus, one can consider it as a five-layer network with 620 edges in the 5 layers. For more information about this dataset, that we call AUCS in the text, readers can refer to \cite{Magnani2013}.\\
%\textbf{Synthetic dataset: } 
\subsubsection{Synthetic dataset }As the real dataset doesnt have have varying properties thus, we created a synthetic dataset. The synthetic dataset consists of two-layer graphs with each layer having 10,000 nodes, where each layer graph is based on the Barabasi-Albert (BA) model \cite{barabassiModel} using the network generation framework presented in \cite{magnani2013formation}. We created 11 such multiplex networks with varying inter-layer similarity values, ranging from 0 to 100 with an interval of 10\%.

%The missing cardinality of nodes and edges have different impact on the accuracy of the collected dataset. Compared to missing values of edges, missing values of nodes can result in a disconnected graph. To understand this better
%We first explain the datasets and then report our results on flatten network and as well as measured values on multilayer measurement.
%\subsection{Datasets}
%\noindent
%\textbf{1. AUCS Dataset}
%The dataset describes various kind of relations among the employees of a department in the university and
%\noindent
%\textbf{1. Airline dataset}
%The dataset used by authors in \cite{Cardillo2013}, is a multiplex network, where nodes represents the airports in Europe and edges if a particular airline fly between these two airports. The network consists of thirty-seven layers, where each layer corresponds to a different airline.
%and as well as on multilayer measurement.We first measure the effect of missing data on the flatten network properties.

\subsection{Results}
%\vspace{-4pt}
In this section we present our experiment results for flatten and multiplex network properties.
%\vspace{-4pt}
%\subsubsection{Flatten network properties }\label{sec:Eval:FlatNwPro}
We first present the results w.r.t effect of missing data on the flatten network.



\begin{figure*}[ht]
%\vspace{-10pt}
  \begin{center}
    \subfigure[Facebook]{\label{fig:FBXRelv}\includegraphics[width=0.3\textwidth]{XRel-FB4.pdf}}
    \subfigure[Lunch]{\label{fig:LNXRelv}\includegraphics[width=0.3\textwidth]{XRel-LU4.pdf}}
    \subfigure[Leisure]{\label{fig:LEXRelv}\includegraphics[width=0.3\textwidth]{XRel-LE4.pdf}}
    \subfigure[Work]{\label{fig:WOXRelv}\includegraphics[width=0.3\textwidth]{XRel-WO5.pdf}}
    \subfigure[Coauthor]{\label{fig:COXRelv}\includegraphics[width=0.3\textwidth]{XRel-CO4.pdf}}
    %\subfigure[Facebook]{\label{fig:FBXRelv}\includegraphics[width=0.19\textwidth]{XRel-FB4.pdf}}
%    \subfigure[Lunch]{\label{fig:LNXRelv}\includegraphics[width=0.19\textwidth]{XRel-LU4.pdf}}
%    \subfigure[Leisure]{\label{fig:LEXRelv}\includegraphics[width=0.19\textwidth]{XRel-LE4.pdf}}
%    \subfigure[Work]{\label{fig:WOXRelv}\includegraphics[width=0.19\textwidth]{XRel-WO4.pdf}}
%    \subfigure[Coauthor]{\label{fig:COXRelv}\includegraphics[width=0.19\textwidth]{XRel-CO4.pdf}}
  \end{center}
 % \vspace{-10pt}
  \caption{xRelevance on Five Layers.} \label{fig:XRelv}
 % \vspace{-10pt}
\end{figure*}

\begin{figure*}[th!]
%\vspace{-20pt}
  \begin{center}
    \subfigure{\label{fig:center}\includegraphics[width=1\textwidth]{StatsRelvSyntheticData1.png}}
    %\subfigure{\label{fig:center}\includegraphics[width=1\textwidth]{StatsRelvSyntheticData1.png}}
  \end{center}
  \caption{Effect of missing Data when data is removed from one of the layer.}
  %\vspace{-15pt}
  \label{fig:SimMisDataLayers}
 % \vspace{-10pt}
\end{figure*}

%\noindent\textbf{Effect of similarity: }
\subsubsection{Effect of similarity }
The similarity score of all the combined five layers of AUCS data is 0.009, with a similarity score of any two networks ranging from 0.339 to  0.058. To understand the effect of similarity, we selected two layers having the most and the least similarity values to rest of the layers. The $Lunch$ layer has the most similar value when compared to all the other layers,
%based on average values with all the other layers,
and $Coauthor$ is the least similar layer to others. To see the effect of missing data, we start removing the edges from both these layers individually. Figure \ref{fig:EffOfSim} shows the effect of removal of edges from 5\% to 50\% in these two individual cases on Diameter (D), Clustering Coefficient (CC) and Average Path Length (APL) on Lunch (LU) and coauthor (CO) layers. Readers can refer to Table \ref{Tbl:VariablesTable} for all the short notations being used in the various experimental results. The figures are represented using monochromatic colour variations. Each box shows the \% variation of change of value w.r.t original value. The box of the colour for the corresponding missing \% and the respective property becomes more intense (thus darker in colour) with the increase in variation.

The lunch layer is the most similar layer to the overall network, compared to the other layers so one can expect that the effect of removal of the edges should be minimum. However, the absolute number of lunch edges (193) is almost 8 times higher than coauthorship (21). Thus, the removal of coauthor edges has not affected the properties as compared to removal of lunch layer. The removal of the edges has the least effect on the diameter. However, the removal of the 50\% of lunch edges has more negative impact on the other two structural properties of the graph in case of lunch layer. As the similarity score among layers is very less, thus, this real dataset is not ideal to see the effect of similarity values. To complement this, we present the next set of experiments on the synthetic dataset, which has a varying values of similarity.

%We picked layers with the highest (0.3391003: lunch and work- LW) and lowest (0.05839416: coauthor and facebook - CF) similarity score values.


\begin{table}[h!]
%\vspace{-10pt}
  \begin{center}
    \begin{tabular}{| c|  c |c |c|}
    \hline
    Layer Removal  & D         & CC                 & APL \\\hline
    \{CO,LU\}      & \{0,0\}   & \{0.25,11.55\}     &\{0.05,2.73\}  \\\hline
    \{FB,WO\}      & \{0,50\}  & \{3.40,7.28\}      & \{4.82,25.90\} \\\hline
    \{LU,WO\}      & \{0,25\}  & \{10.99,12.67\}    & \{2.65,21.58\} \\\hline
    \{WO,LE\}      & \{0,25\}  & \{0.83,1.08\}      & \{11.30,14.01\}  \\\hline
    \{LE,WO\}      & \{0,25\}  & \{1.12,1.08\}      & \{1.69,14.01\} \\\hline
    \end{tabular}
    %\vspace{-2pt}
  \end{center}\label{Tbl:DiffComb}
   \caption{Effect of Layers Removal}
  %\vspace{-4pt}
\end{table}



%\begin{figure}[ht]
%  \begin{center}
%    \subfigure{\label{fig:center}\includegraphics[width=1\textwidth]{Figures/2LayersRemoval.png}}
%  \end{center}
%  \caption{Removal of 2 Layers.}
%  \label{fig:Rem2Layers}
%\end{figure}






\subsubsection{Variation in similarity score of the layers }
When the similarity of the layers tends to 1 ($Sim(l_{i=1}^L)$ $\rightarrow$ 1), that is the networks in the individual layers are more similar to each other then the absence of nodes/edges in one layer does not affect much the flatten network properties. However, when the similarity score is low then the absence of nodes in one layer affects the flatten network's properties more adversely. This is established by our simulation on synthetic networks. Figure \ref{fig:MLVarySim} shows the results for three graph properties. In 11 multi layer networks, with varying similarity values (on the X-axis), we remove the edges from 1 to 10 \% (on the Y-axis) and calculate the three graph properties (D, CC, APL). The least common affected is the diameter among all the three. In all the three properties, we have not been able to find a consistent behavior with varying values. However, it is commonly observed that, with the decrease of similarity among layers and with an increase in missing values, more variation is observed.

\subsubsection{Effect of layer removal }
Table \ref{Tbl:DiffComb} shows the effect of layer removal on the flatten network properties on all the five layers, namely Facebook (FB), Lunch (LU), Work (WO), Leisure (LE) and Coauthor (CO). We take five individual cases, where we removed each layer and kept the four other layers to see the effect. To understand the effect of removal of a similar layer on the network, as a next step, we then remove the layer which is the most similar to remaining layers. We then notice the effect on the structural properties of the flatten network. We only removed up to two levels, as after that the graph becomes disconnected. Column 1 of the table shows the pair of layers removed one after the other and the corresponding column shows the values of percentage variations in D, CC, and APL properties after the removal of successive layers. A common observation is that there is a monotonic non-decreasing variation in the properties of the parameters.

%\textbf{To see the effect of layers: }By using real dataset, we describe the effect of missingness of layers' information in section \ref{sec:Eval:FlatNwPro}.
\subsubsection{Multilayer network properties }
 %\textbf{XRelevance}
Figure \ref{fig:XRelv}, shows the xRelevance values for the five layers of the real dataset. We removed from 5\% to 40\% of the edges. In all the five layers there is a consistent change in xRelevance values, thus, signifying the importance of missing data. To see the importance of similarity on xRelevance, we performed experiments on synthetic dataset.
%\raj{I think a better way would be to see the importance of a layer, after removing like 80 \% of data from layer Lunch and see if any other layer becomes more important, but then that is intuitive. Let me know if there is any better way to represent or show the information.}
Figure \ref{fig:SimMisDataLayers} shows the impact of various similarities on xRelevance values on the synthetic dataset. The X-axis shows the missing data percentage and on the Y-axis the xRelevance values are plotted with different variations of similarity. A common observation in all the multilayer networks (with different similarity levels) is that with an increase in missing data, the gap between the xRelevance of layer 1 and layer 0 increases. %The gap is widened with decrease in similarity values as the importance of the layer increases when the other varying layer's data decreases.
These results show that there is a change in the xRelevance values on different layers and that as the data gets more and more incomplete on one of the layers, the relative importance of all the layers is affected. This is expected from the definition of xRelevance, and highlights how the presence of multiple layers introduces an additional level of complexity to the problem of missing data.

\begin{table}[!htbp]
  \small
	\caption{Legends used in various figures }
	
    \begin{tabular}{|p{2.4cm}|p{1.5cm}|p{2.8cm}|}
    \hline
    %\multirow{1}{*}{Type} & \multirow{1}{*}{Legend or Notation} & \multirow{1}{*}{Definition} \\
    Type & Legend or Notation & Definition \\

	\hline
     \multirow{5}{*}{Network}
        & FB & Facebook  Layer.\\
		& LU & Lunch Layer.\\
        & WO & Work  Layer.\\
        & LE & Leisure  Layer.\\
        & CO & Coauthor  Layer.\\
  \hline
     \multirow{3}{*}{Network Properties}
        & D & Diameter.\\
		& CC & Cluster Coefficient.\\ 		
		& APL & Average Path Length.\\
				
\hline
     \multirow{2}{*}{Parameters}
 		& S & Similarity.\\
		& M & Missing.\\
	\hline
	\end{tabular}%
  \label{Tbl:VariablesTable}%
\end{table}%




 \begin{comment}
 To see the effect of similarity score, we removed once the edges from LW and then again from CF. We noticed that the network properties in case of LW changes rapidly and more faster as compared to CF. This establishes the fact that similarity score is a deciding factor when the edges are missing.

We then remove the nodes with some percentage in each of the network to see the effect.

To see the effect of layers removal. When removing lunch (with has a similar layer: lunch) and when removing a least similar layer that is coauthor.

In another case, we remove the layers like 1, 2 3: This is arbitrarily. Removal of 1,2,3 4 (  4 doesnt make any sense but it has to be removed to see the effect of single layer) and 2 layers and so on.


The value shows that the networks are value


\textbf{ Vertex / Edge removal}

\subsubsection{ Multiplex network measures}
\textbf{ Vertex / Edge removal}
\end{comment}

Formalism1.tex
%\vspace{-4pt}
\section{Methodology }\label{sec:formalism}
%\vspace{-10pt}
%(Conceptual/Theoretical) What's more on multiplex networks (2 pages, 2 days -- Rajesh)
%Formalism ----  Modelling missing data -- Theoretical Analysis
In this section, we first describe our methodology to understand missing data in single networks and then extend it to multiplex networks.

\subsection{Single layer networks}
%\vspace{-4pt}
A network dataset consists of i) a set of nodes ($S_N$), and ii) a set of edges ($S_E$), essentially representing a graph structure $G$($S_{N}$, $S_{E}$). In our experiments we focus on undirected networks. We consider two sets $M_N$ and $M_E$, containing respectively a list of missing nodes and edges. We then study the effect of these missing data on a set of network properties, such as diameter, average path length and clustering coefficient. These properties are indicated as $\mathrm{NP}_G$. The accuracy (or precision $P$) of the network properties for $G$ depends on how close the collected data is to the original graph. The precision of the graph properties of the incomplete graph $G'$ tends to 1 ($P$($\mathrm{NP}_{G'}$) $\rightarrow$ 1) when the cardinality of the missing data tends to zero ($\mid$ $M_N$ $\mid$ $\rightarrow$ 0 and $\mid$ $M_E$ $\mid$ $\rightarrow$ 0). The objective of our empirical study is to estimate the behaviour of $P$ at different levels of missingness by randomly removing edges and vertexes to simulate different levels of missing data. %Thus, the accuracy of the properties in the collected data depends on the two parameters that is on the cardinality of missing nodes and edges (or relations) of the graph.

%Let the collected data is represented by $G^{'}$ and original data present at the source (Facebook, Twitter etc.) is $G$.

\subsection{Multiplex networks}\label{sec:forml:ML}
%\vspace{-4pt}
In multiplex networks, in addition to nodes and edges there is an additional \emph{layer} parameter. Each layer represents a different type of connection. Formally, a multiplex network can be represented as a graph structure $G_{ML}$=\{$N$, $E$, $L$\}, where $N$ is the set of nodes, $E \subseteq N \times N \times L$ is the set of edges, and $L$ represents the set of layers. Thus, in a multiplex network, the accuracy of the graph properties depends on three parameters ($N$, $E$, and $L$). Furthermore, the network properties in a multilayer network can be categorised in two ways. Firstly, which we termed as \emph{multiplex network properties}, a set of properties explicitly considering the layers. However, a typical way of studying a multiplex network consists in merging (some of) the layers into a single one so that traditional methods can be applied. The resultant flatten network is formed by union of all the nodes and edges of various layers of a multiplex network. In this case we use traditional single-layer metrics that we call \textit{flatten network properties}.

\subsubsection{Multiplex network properties }
In many recent works such as \cite{MatteoMuldiDimNw}, the authors have defined various multi-dimensional measures. Out of various defined measurements, in this preliminary work we focus on the exclusive relevance (or xRelevance) \cite{Berlingerio2012a}. Readers can refer to \cite{MatteoMuldiDimNw} for more properties.
For each node, xRelevance describes the importance of a particular layer in the network to exclusively reach some neighbours. \textit{xRelevance computes the fraction of neighbours directly reachable from node n following edges belonging only to a layer L}. As a consequence, removing that layer the connections with those neighbours would be lost. For example, consider a node in a multiplex network with two layers A and B, with relevance of A higher than B. If more edges are removed from A, then the relevance w.r.t A can decrease and the one w.r.t B can increase.
%However, this measure might not rightly capture the information about the connectivity of a node. To compensate, the authors introduce a variant of it which they termed it as xRelevance. \textit{xRelevance computes the fraction of neighbors directly reachable from node n following edges belonging only to a layer L}.


\subsubsection{Flatten network properties }
In the due process of flattening the multilayer networks, the resultant final flatten network very much depends on how much similar the networks in individual layers are. The Jaccard similarity between the networks of two layers $L_i$ and $L_j$ is computed as the ratio of cardinality of the intersection of the edges of two networks to the cardinality of union of edges of two networks. This notion can be extended for any number of layers. For any number of layers $l$ = 1 to L, a generalised formal representation is following,
\begin{equation} \label{EQ:Sim}
%Sim(L_i, L_j) = {\frac{\mid G_{L_{i}} \cap G_{L_{j}} \mid}{\mid G_{L_{i}} \cup G_{L_{j}} \mid}}
Sim(l_{i=1}^L)=\frac{\bigcap_{i=1}^L G_i}{\bigcup_{i=1}^L G_i}
\end{equation}


\begin{figure}[ht!]
%\vspace{-20pt}
  \begin{center}
   \subfigure[Diameter]{\label{fig:LC-Dia}\includegraphics[width=0.35\textwidth]{LC-Dia5.pdf}}
   \subfigure[Cluster Coeff.]{\label{fig:LC-CC}\includegraphics[width=0.35\textwidth]{LC-CC5.pdf}}
   \subfigure[Avg. Path Length]{\label{fig:LC-APL}\includegraphics[width=0.35\textwidth]{LC-APL5.pdf}}
  %  \subfigure[Diameter]{\label{fig:LC-Dia}\includegraphics[width=0.325\textwidth]{LC-Dia4.pdf}}
  %  \subfigure[Cluster Coeff.]{\label{fig:LC-CC}\includegraphics[width=0.325\textwidth]{LC-CC4.pdf}}
  %  \subfigure[Avg. Path Length]{\label{fig:LC-APL}\includegraphics[width=0.325\textwidth]{LC-APL4.pdf}}
  \end{center}
  %\vspace{-20pt}
  \caption{Comparison of Lunch and Coauthor layers.}
  \label{fig:EffOfSim}
  %\vspace{-10pt}
\end{figure}




\begin{comment}

\begin{equation} \label{EQ:Sim}
%Sim($L_i$, $L_j$) = {\frac{$\mid$ $G_{L_{i}}$ $\cap$ $G_{L_{j}}$ $\mid$}{$\mid$ $G_{L_{i}}$ $\cup$ $G_{L_{j}}$ $\mid$}}
Sim(L_i, L_j) = {\frac{\mid G_{L_{i}} \cap G_{L_{j}} \mid}{\mid G_{L_{i}} \cup G_{L_{j}} \mid}}
%a=\frac{\bigcup_{i=1}^L x_i^2}{\bigcap_{j=1}^N y_j^2}
\end{equation}


  The P($GP_G$) --$>$ 1, when the set $M_n$  --$>$ 0, $M_v$ --$>$ 0, and $M_l$  --$>$ 0.


\raj{Are we going to talk about properties such as Neighborhood etc, which we can measure using Matteo's library ? Multi-layer path length could be one such property ? Cluster coefficient , multi dimensional distance (or may be it is on similar lines of path length)}
network, relevance


\textbf{Effect of Missing Nodes}
In case of WS, even with the removal of 0.1 \% of least centrality nodes, the graph becomes disconnected. In case of BB, the graph remains connected till the removal of 0.7 \% least centrality nodes. We then measure the percentage change of graph properties for BB. Figure \ref{fig:SLNodes} shows the change in graph properties that is Diameter (D) , cluster coefficient (CC) and average path length (APL) for the \% removal of nodes from 0.1 \% to 0.7 \% to the original graph. The Figures are represented using monochromatic color variations. The box of the color for the corresponding Missing \% and the property becomes more intense (thus darker in color) with the increase in variation.


\begin{figure}[t]
%\vspace{-20pt}
  \begin{center}
    \subfigure[Barabassi Model]{\label{fig:BBGraphProp}\includegraphics[width=0.5\textwidth]{Figures/BBRemoveNodesProp.png}}
    %\subfigure[Watt Strogatz]{\label{fig:WSGraphProp}\includegraphics[width=0.4\textwidth]{Figures/WSDiaCcApl.png}}
    %\subfigure[Total Random]{\label{fig:barabassi-TR-md}\includegraphics[width=0.4\textwidth]{TR-MesgDism.png}}
    %\subfigure[DBLP]{\label{fig:dblp-md}\includegraphics[width=0.4\textwidth]{DBLP-MesgDism.png}}
  \end{center}
  %\vspace{-20pt}
  \caption{Effect of Missing Nodes in Single Layer Network.} \label{fig:SLNodes}
  %\vspace{-15pt}
\end{figure}

\textbf{Effect of Missing Edges}
To understand the effect of the missing edges, we removed the edges both in WS and BB graphs. In case of BB, till the removal of 16 \% edges the graph was connected and in case of the WS till 22 \%. Figure \ref{fig:SLEdges} shows the effect of removal of edges on three graph properties. In all the properties it is observed that with the increase in missing edges, the variation also increases. The diameter is least affected among all the three properties. However, there are few exceptions, which are attributed because of removal of critical nodes, which might have high centrality value. Figure \ref{fig:SLEdges} also signify that removal of the edges have a common effect on graphs with different graph models.

\begin{figure}[t]
\vspace{-20pt}
  \begin{center}
    \subfigure[Barabassi Model]{\label{fig:BBGraphProp}\includegraphics[width=0.45\textwidth]{Figures/BBSingleNWProp.png}}
    \subfigure[Watt Strogatz]{\label{fig:WSGraphProp}\includegraphics[width=0.45\textwidth]{Figures/WSDiaCcApl.png}}
    %\subfigure[Total Random]{\label{fig:barabassi-TR-md}\includegraphics[width=0.4\textwidth]{TR-MesgDism.png}}
    %\subfigure[DBLP]{\label{fig:dblp-md}\includegraphics[width=0.4\textwidth]{DBLP-MesgDism.png}}
  \end{center}
  \vspace{-20pt}
  \caption{Effect of Missing Edges in Single Layer Network.} \label{fig:SLEdges}
  %\vspace{-15pt}
\end{figure}



%\textbf{Different graphs, different models ,has any effect on the percentage increase.}
% Also, properties are very much dependent on what kind of nodes are missing from the collected data set. For example, if a central node is missing then it is going to affect diameter and average path length of the network compared to cluster coefficient.


The first column is the diameter, second cluster coefficient and third is the
Table \ref{Tbl:SlNetProp} shows the properties of the original network and when the data is missing from this original graph. As the number of cardinality of missing data increases, the difference between the network properties of the original and sampled graph also increases. To confirm this, we create 2 networks based on (i) barabassi based power law model \cite{barabassiModel}and on (ii) wattz strogatz model \cite{watts1998cds}.

We then carefully removed the most centrality nodes and corresponding edges to show that these edges diameter and average path length than the cluster coefficient. \fixme{Table or some figures for this.} Is it going to be based on cluster coefficient of the nodes or degree or centrality
We then start removing top centrale nodes, like 1,2 3, 10 percentage and see the effect on other properties.


%\begin{figure}[ht]
%  \begin{center}
%    \subfigure{\label{fig:center}\includegraphics[width=0.3\textwidth]{Figures/BBSingleNWProp.png}}
%  \end{center}
%  \caption{Effect of Missing Data in Single Layer Network.}
%  \label{fig:BBGraphProp}
%\end{figure}


%To analyze the effect of missingness in layers, we used real data and describe tA Figure similar to \ref{fig:Rem2Layers} his missing. We can miss it here, because we have a figure corresponding to this in real dataset. So this can be ignored.



The Table \ref{Tbl:DiffCaseOfNVL} provides the importance of various parameters.

\raj{@Matteo: You want to make the project(library of multi layer network) open to other people. We can post a link here, in the paper. That we use jacard similarity which we used in our library, the link of the library is xyz.}

\raj{1 Figure when data is missing from layer 1, when the data is missing from randomly from 2 layers}
\end{comment}

Intro.tex
%\vspace{-4pt}
\section{Introduction }\label{sec:Intro}
%\vspace{-10pt}
%\raj{write something about the sampled survey as well, like in socialogical studies or experimental studies. Survey as well. Networks have always interacted the researchers. start with something about networks, then mode to real world online and as well as offline. Real, vast amount of data and that in social network.}

%\matteo{As for the abstract, I would like to go a little more directly to the main topic of the paper -- I assume that SocInfo reviewers would like to skip the standard \emph{"social networks are important"} paragraph, although I probably suggested it myself when we discussed the paper structure.}
%The field of network science, has always fascinated researchers from various backgrounds such as social scientists, biologists, physicists and computer scientists. One of the prominent technique to understand the structure of networks and various types of interactions happening among nodes, is collect the network data and analyze.
Missing data is one of the main problems in social network analysis.
In most empirical studies data incompleteness is unavoidable: this applies to traditional studies in social sciences, with data coming from field experiments such as \cite{Roethlisberger1939}, \cite{Travers69anexperimental}, \cite{Bearman2002}, but also to studies targeting online sources like Facebook or LinkedIn, where the large amount of data that can be automatically collected does not necessarily imply completeness or prevent statistical biases. In all these cases it is fundamental to be able to estimate the impact of missing data on the outcomes of the network analysis process, otherwise the results may not accurately represent the studied social system.
%However, in the due process of collection of network data, some of the data gets missed, which we term as missingness of data in the collected data.

%\matteo{@Rajesh: This is the \emph{"social networks are important"} paragraph that I would skip, and keep for a following paper to be submitted to a less focused venue. Or did you have a specific point that I am missing? I added a sentence to the previous paragraph to cover the aspect of small-big data.} In comparison to social experiments which generally have a small amount of data, scientists have started looking for alternative means to look for large set of social network data. Unarguably, the social network platforms have a vast amount of data as the online social networks has created a lot of enthusiasm among people these days. This can be validated by the presence of  a large number of active users on the social platforms. For example, Facebook, has estimated number of more than one billion\footnote{http://www.statisticbrain.com/facebook-statistics/} active users, on Twitter the number of active users are more than 250 million users\footnote{http://www.statisticbrain.com/twitter-statistics/}. Similarly, in LinkedIn, which is a professional social networking site has active users of almost 300 million \footnote{http://www.bidnessetc.com/23403-linkedin-expected-to-beat-estimates-despite-slow-user-growth/}.  To understand the various aspects of the networks and users' interactions, researchers generally collect data from these social networking platforms. Again, in the due process a lot of data gets missed.

In recent years, researchers have taken a step forward by considering systems of multiple interdependent networks \cite{Kivela2014}.
%Thus, multilayer networks are the networks, in which various networks are connected with each other.
For example, consider the case of Facebook and LinkedIn.
%Many of the users present on Facebook are also present on LinkedIn. However, t
These networks are connected with each other through the users having accounts on both of them.
This scenario introduces multiple opportunities and challenges.
%\matteo{I extended a bit the discussion here. Please, check if it makes sense.}
If there is evidence that users are connected to the same individuals on the two networks, then the overall effect of missing data can be reduced: information missing from one network can be recovered from the other.
%For more details, please see section \ref{sec:prelim:Singnetw}.
At the same time, collecting data from multiple networks can be more difficult, as each network has its own technical restrictions. As a result, new problems can emerge, including data missing in different ways depending on the network and new types of missing data, e.g., concerning identity relationships between user accounts in the different networks.

The general importance and practical relevance of the problem together with the differences and extensions with respect to the single-network case require a significant research effort. In this paper, we move a first step in this direction: we raise awareness of this problem and investigate some basic issues, more specifically new types of missing data and their effect on the main network properties.
%\vspace{-5pt}
\subsection{Delimitation}
%\vspace{-5pt}
%\matteo{I am moving this here from the previous sub-section as I think it is on what we do not do. Feel free to correct me.}
%Missingness of data in the collected data can affect the properties of the network. As it cannot provide the exact properties of the original network present in the social platform or in the real world.
Various imputation techniques have been proposed in the past to recover or estimate missing data \cite{Sadikov2011}, \cite{Bagrow2013}.
%However, these estimated or probability based techniques
While no general approach can guarantee that the new values do not introduce any bias, imputation methods as well as approaches based on data removal are often used in practice. However, attempts to improve the quality of the data are orthogonal to our work, where we focus on estimating the impact of missingness and not on repairing it.
%for the missing data can fill the gap original gap in the data with full accuracy. \fixme{Fill some papers from \cite{Kossinets_SocNet2005}}
In addition, during the process of data collection some errors about nodes, edges and network attributes can be introduced due to wrong experimental settings or technical problems. %That is some information about the nodes or edges might be wrong.
This aspect is not covered in this work, because missing and wrong information require different treatments and can be considered two related but distinct problems.
% Neither we are proposing any data recovery schemes for the missing data such as proposed in the past \cite{Sadikov2011}.

%\matteo{This paragraph seems a repetition of the first contribution (next paragraph) or an extension of concepts touched in other parts of the introduction. Please, consider merging it with that - or even removing it.} There are various reasons for missingness of data, for example, in a social experiment a participant's non-divulgence of some information. While downloading the data from a social platform, some of the data might get missed due to various technical reasons, for example, the crawler cannot download the data because profiles are not public. %Please see section \ref{sec:prelim} for more details.

\subsection{Contribution and Method}
In this work, we only deal with the impact of missing data on the networks' properties and we provide the following main contributions:
\begin{enumerate}
\item We classify the possible types of missing data in multiplex networks.
%Most of the reasons for missing data in social networks mentioned in \cite{Kossinets_SocNet2005} are also the cause of missingness in multilayer networks as well. In addition to that we proposed a new cause of missingness  which is solely applicable to multilayer networks.
\item We characterise how some major single and multiplex network properties are distorted by different types and levels of missing data.% in multiplex networks.
\end{enumerate}


We address the first item starting from known classes of missing data for single networks and discussing how these extend to the multidimensional case. The second contribution is obtained through simulation studies on synthetic and real data.

The rest of the paper is organised as follows. Section \ref{sec:prelim} summarises known reasons for missing data in social networks and discusses how this extends to multiplex networks. In Section \ref{sec:formalism}, we present our methodology to understand the impact of missing data on network properties in multiplex networks. We then evaluate the impact of missingness in multiplex networks in Section \ref{sec:eval}. We draw our conclusions and future extensions of our work in Section \ref{sec:concl}.

\begin{comment}
\subsection{Some more stuff}
We now describe something

%\begin{figure}[ht]
%  \begin{center}
%    \subfigure{\label{fig:center}\includegraphics[width=0.3\textwidth]{Figures/Figure1.png}}
%  \end{center}
%  \caption{Some caption.}
%  \label{fig:ofwhat}
%\end{figure}





\subsection{Background and Motivation}\label{sec:Intro:background}
%\subsubsection{Background and Motivation: }\
abc
\subsection{Motivation }
What is the motivation for this paper

\subsection{Disclaimer/Assumptions}
What about the things we are not covering ?

\subsection{Goal }
The goal of this paper is to provide ... ... Thus, we provide ...
%What is the goal of this paper $?$ Present a decentralized architecture

\subsection{Contribution }
The major contributions of the proposed mechanism in this paper are:
\begin{enumerate}
\item We introduce various reasons for the missingness in multilayer networks.
\item We also introduce a formal model to understand the missingness of data in multilayer networks.
\item abc \fixme{Is it a contribution}
\item We have verify our approach with the formal model. \raj{@All: Add some complex equations.}
\end{enumerate}
\end{comment}



MainFile.tex
%\documentclass{llncs} % llncs, elsevire style
\documentclass[10pt,conference,compsocconf,letterpaper]{IEEEtran} % 2 page IEEE style
%\documentclass{acm_proc_article-sp} % ACM Style

\usepackage{times}
%\usepackage[pdftex]{color}
\usepackage[pdftex]{color, graphicx}
\usepackage{subfigure}
\usepackage{comment}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{mathtools}
\usepackage{amsmath}
\usepackage{multirow}
%\usepackage[cmex10]{amsmath}
%\usepackage{verbatim}

\newcommand{\fixme}[1]{{\em\bf{[FIXME: #1]}}}
\newcommand{\raj}[1]{{\color{red} *** {\textbf{Rajesh: }}\color{blue}{#1}}{\color{red} ***}}
\newcommand{\matteo}[1]{{\color{red} *** {\textbf{Matteo: }}\color{blue}{#1}}{\color{red} ***}}
\newcommand{\danilo}[1]{{\color{red} *** {\textbf{Danilo: }}\color{blue}{#1}}{\color{red} ***}}
\newcommand{\oq}{``}
\newcommand{\cq}{''}

%\title{Missing data in multiplex networks: a preliminary study \small{(short paper)}}
\title{Missing data in multiplex networks: a preliminary study }
%%LNCS Name Style - - Please do not delete this
%\author{Rajesh Sharma$^{1}$
% \and Matteo Magnani$^{2}$ \and Danilo Montesi$^{1}$ \institute{University of Bologna, Italy \\ \{rajesh.sharma, danilo.montesi \}@unibo.it \and Uppsala University, Sweden \\ matteo.magnan@it.uu.se}}

 %IEEE Name Style - Please do not delete this
 
\author{
    \IEEEauthorblockN{Rajesh Sharma\IEEEauthorrefmark{1}, Matteo Magnani \IEEEauthorrefmark{2}, Danilo Montesi\IEEEauthorrefmark{1}}
    \IEEEauthorblockA{\IEEEauthorrefmark{1}University of Bologna, Italy
    \\\{rajesh.sharma, danilo.montesi\}@unibo.it}
    \IEEEauthorblockA{\IEEEauthorrefmark{2}Uppsala University, Sweden
    \\\{matteo.magnan\}@it.uu.se}
}


%\author{\IEEEauthorblockN{Rajesh Sharma$^{1}, Matteo Magnani$^{2}$, \and Danilo Montesi$^{1}$ }
%\IEEEauthorblockA{School of Computer Engineering\\
%ABC University\\
%Country/City\\
%\texttt{\{email id1,email id1,email id1,email id1\}@institue.edu.xg} } }


% IEEE Name Style - Please do not delete this
\newlength{\LL}

\begin{document}
\maketitle

\begin{abstract}
%\matteo{I tried to put immediate focus on the missing data problem. Please, check if it reads well.}
%Multi layer networks have recently attracted the attention of researchers from various arenas. Physicist, computer scientist and biologist all have started looking into this area. As it gives a clear and bigger picture of the real world network compared to a single layer network.
A basic problem in the analysis of social networks is missing data. When a network model does not accurately capture all the actors or relationships in the social system under study, measures computed on the network and ultimately the final outcomes of the analysis can be severely distorted. For this reason, researchers in social network analysis have characterised the impact of different types of missing data on existing network measures.
Recently a lot of attention has been devoted to the study of multiple-network systems, e.g., multiplex networks. In these systems missing data has an even more significant impact on the outcomes of the analyses. However, to the best of our knowledge, no study has focused on this problem yet.
%as in single layer networks, the problem of missing data in multilayer is also naturally observed when the researchers collect the multi layer networks' dataset. %However, inherently because of complexity, missingness impacts the multilayer network structure property more adversely.
This work is a first step in the direction of understanding the impact of missing data in multiple networks. We first discuss the main reasons for missingness in these systems, then we explore the relation between various types of missing information and their effect on network properties. We provide initial experimental evidence based on both real and synthetic data.
\end{abstract}

\textbf{Keywords:} missing data, multilayer networks, multiplex.

\input{Intro} % -- ?
\input{Preliminaries_short} % The single network case (1.5 pages, 2 days -- Rajesh.)
%\input{Approach} %
\input{Formalism1} %(Conceptual/Theoretical) What's more on multiplex networks (2 pages, 2 days -- Rajesh)
%\input{ToDo} % Qs as we think about it
\input{Eval1} %-- Rajesh
%\input{MethodAndEval_short}
%\input{Related} % -- Matteo and Rajesh?
\input{Conclusion} % -- ?


\bibliographystyle{abbrv}
\bibliography{disco,additional_refs}
\label{sec:References}
\end{document}

Preliminaries_short.tex
%This is version ) of approach section
%\vspace{-4pt}
\section{Missing data in simplex networks}\label{sec:prelim}
%\vspace{-10pt}
%In this section, we explain various reasons for the missing data in single networks (in Section \ref{sec:prelim:Singnetw}). Later, in section \ref{sec:Prelim:MissInML}, we explain how few existing reasons of missigness in single networks can also be a cause in multi layer networks. In addition to this we introduce a cause of missignness in multilayer networks.

%\raj{@Matteo: Connection between above and this paragraph is missing and similarly after this paragraph as well.}
%The missingness of the data can be categorized into three different categories \cite{LittleAndRubin}. 1) The data is said to be ``missing completely at random'' (MCAR), When the data is missing totally at random. In other words, the data is not missing because of some values of a variable. For example, non-appearance of some participants in an experiment. 2) In compared to MCAR, the data for a particular variable might be missing because of its dependency on other variables. In that case, it is said to be as ``missing at random'' (MAR). For example, older people are reluctant to divulge their income details. 3) A missing data not falling in the above two classifications is called ``not missing at random'' (NMAR). There are particular reasons behind the missingness of the data. In other words, the variable for which the data is missing due to some specific reasons. These factors are generally external and not in control of the experiment. For example, low income participants deliberately skip the income field.


%\begin{comment}
%\subsection{Types of missing data}\label{sec:Prelim:Types}
%
%The data from the sampled dataset could be missing for various reasons. Little and Rubin \cite{LittleAndRubin} define three different classes of missingness.
%
%\subsubsection{Missing completely at random (MCAR)}
%When the data is not missing because of some values of a variable, the missingness of the data is said to be as missing completely at random. In simple words the data is missing totally at random. For example, non-appearance of some participants in an experiment. % In a network example, while crawling a social network site if the profile of a user is not public then it will not appear in the crawled dataset.
%
%\subsubsection{Missing at random (MAR) :}
%The data for a particular variable might be missing because of its dependency on other variables. In that case, it is said to be as Missing at random. For example, older people are reluctant to divulge their income details.
%
%\subsubsection{Not missing at random (NMAR) :}
%A missing data not falling in the above two classifications is called ``not missing at random''. There are particular reasons behind the missingness of the data. In other words, the variable for which the data is missing due to some specific reasons. These factors are generally external and not in control of the experiment. For example, low income participants deliberately skip the income field.
%\end{comment}

%\subsection{Missingness in Single Layer Networks}
\label{sec:prelim:Singnetw}
%In this section, we describe various reasons of  missingness of the network data.

For single-layer networks, Kossinets \cite{Kossinets_SocNet2005} describes three main causes of missing data: network boundary specification, survey non-response, and respondent inaccuracy. As a working example for both the single- and multiplex-network cases, consider a network of employees at a University department.
%They are connected because of their interactions with each other.
%We will use this example while trying to explain the reasons of missing data in single as well as later in multi layer networks.

%Some of these employees could be academic and other non-academic type. They are connected because of their interactions with each other. For example, professors generally have to interact among each other for collaboration and academic meetings. Professors interact with non-academic staff because of various administrative and bureaucracy works. Academic and non-academic might also interact with each other because of some social events for example, lunch and department get together. We will use this example, while trying to explain the reasons of missing data in single as well as later in multi layer networks.

%censoring by vertex degree (fixed choice design)
{}
\begin{enumerate}

\item A first source of missing data is known as \emph{network boundary specification problem}, where it is the experimenter who restricts the network
%for consideration
by specifying rules for selection of nodes and relations \cite{lauman}.
%These boundary conditions can affect the network properties due to loss of information.\\
In our University department example, the choice of restricting the analysis to the relations happening inside the institution is an example of boundary problem: two employees who are disconnected inside the department can both work together with a third individual from another department, which makes them closer than the available data would suggest. A second example consists in including only nodes with at least a given degree in the dataset.
%Consider the above example, while researcher might only consider the professional relations existing among the colleagues. Thus, these boundary restrictions might result in loss of some important information about relations among individuals. Few researchers not collaborating in an academic arena might be meeting each other regularly for lunch, outside the department. Thus, a very strict condition on the boundary of an organization can lead to loss of some vital information.\\
%\noindent
%This is more common in intra organization studies where the exclusion of ties existing out of the organization might result in loss of some relations. Consider above example, researchers might loose some information if they only consider the co-authorship relations in the intradepartmental study. Few researchers not collaborating in academic might be meeting each other regularly for lunch. Thus, a very strict condition on the boundary of an organization can lead to loss of some vital information.
This is a choice often made to analyse large networks and is related to the field of network sampling \cite{Leskovec2006,Gjoka2011,Salehi2013}.
%\cite{Sadikov:2011:CMD:1935826.1935844}.
%When the experimenter has access to all data and explicitly selects a subset of it, it can be easier to check for the impact on the outcomes of the analysis.

%Another kind of restriction can be placed on the node selection. For example, an experimenter can select nodes with a degree of two or more. Again, taking the above example, if only a particular kind of relations are considered (for example co-authorship) and few are ignored (for example friendship) then a node might not meet a degree restriction. Thus, restriction on vertex can also lead to missingness of data.
%\matteo{Are these two the only kinds of network boundary problem? E.g., can I censor by vertex attributes instead of degree?}
\item A second source is \emph{survey non-response}, which can also lead to the loss of information \cite{Rumsey1993}. The non-response of a participant to a particular query in the survey can depend on other variables: for example, teenagers might be more willing to reveal their relationships than adults.
%\matteo{do we have a network-related example?}. \matteo{Can we say that this still applies to online social networks?}
When other variables are involved, missing data is normally categorised into three main classes: missing completely at random (MCAR), at random (MAR) and not at random (MNAR). As we are not directly using these classes in this paper, we refer the reader to \cite{LittleAndRubin} for additional details.
%1) The data is said to be ``missing completely at random'' (MCAR), When the data is missing totally at random. In other words, the data is not missing because of some values of a variable. For example, non-appearance of some participants in an experiment. 2) In compared to MCAR, the data for a particular variable might be missing because of its dependency on other variables. In that case, it is said to be as ``missing at random'' (MAR). For example, older people are reluctant to divulge their income details. 3) A missing data not falling in the above two classifications is called ``not missing at random'' (NMAR). There are particular reasons behind the missingness of the data. In other words, the variable for which the data is missing due to some specific reasons. These factors are generally external and not in control of the experiment. For example, low income participants deliberately skip the income field.

%In experimental studies, subjects are free to respond or divulge information about the relations with respect to other participants or in general. The hiding or non-response can also lead to the loss of information \cite{Rumsey1993}. The non-response of a participant to a particular query in the survey might be due to a reason of other variables. For example, it has been observed that older people do not divulge their income. Thus disclose of the monthly income in the survey depends on the age factor.
%swith be due to  loss in the survey might be due participant might not diis could be For example, an individual might not divulge his information about the monthly income if he is
\item Finally, \emph{respondent inaccuracy} concerns the fact that %informant inaccuracy or
%The respondents or
participants often only have a personal perception of their relations with other individuals \cite{Bernard1984,Marsden1990}. %, which may be different from reality. This inaccuracy provided by the informant can also result in loss of information \cite{Bernard1984}, \cite{Marsden1990}.
For example, chances are that A perceives her colleague B as a friend while the contrary is not true. %Thus, the information being provided by subjects are based on cognition and not on reality or actual facts. %This kind of information inaccuracy is totally due to the participants and is difficult to be avoided in some cases as the experimenters are totally dependent on the participants and there might not be any case of cross-checking the information .
\end{enumerate}
%\raj{@All: I have not included any fixme solutions for the 4 problems. If we have space in the end, we might fill it with a line or 2 for each problem with their respective solutions.}

\section{Missing data in multiplex networks}\label{sec:Prelim:MissInML}

%\matteo{@Rajesh, you can move this paragraph to your part\dots} we use the AUCS dataset, which is described in more detail in \cite{Magnani2013}. In the network of employees of a University department (both faculty and administration) the following five kinds of interactions have been recorded: i) lunch, ii) work, iii) coauthor, iv) pleasure, and v) Facebook. Thus, one can consider it as a five-layer network. \matteo{\dots up to here}

%We now extend the example we mentioned in section \ref{sec:prelim:Singnetw}, to describe the reasons of missingness in Multilayer networks. The motivation for this example has been drawn from AUCS dataset, which is described in more detail in \cite{Magnani2013}. In the network of employees of a department in a university some of the nodes could be academicians and other administrative. Nodes interact with each others for various reasons - i) lunch, ii) work, iii) coauthor, iv) pleasure, and v) Facebook. Thus, one can consider of it as a five layer multi layer network. These five layers are connected with each other because either the nodes have their presence on multiple networks or nodes are friends on another layer.


%, which is confirmed by the results (Please see Section \ref{sec:forml:ML} and \ref{sec:eval}).
%If an important chunk of information is missing from the layer itself, then this can affect the multilayer metrics. For example, users might not be willing to share (i) their presence on the networks they are present or (ii) the colleague's information they generally go out for leisure. Thus, non-divulgence of the information affects the three aspects (1) Layers: disappearance of layers (2) Relations: Disappearance of relations or edges (3) Nodes: Disappearance of nodes from a particular layer.  In this section, we define the sources of missingness of data in a multi layer network.

All the sources of missing data in single networks are also applicable to multilayer networks, but they are extended and complemented by others.
%In addition, we introduce another reason which could be the source of missingness of data in multilayer networks.
\begin{enumerate}
\item The \emph{network boundary specification problem} can be reinterpreted on multiple dimensions. In Figure~\ref{fig:miss-mpx-bound} we show a multiplex network where individuals can be connected on a \emph{work} layer or a \emph{friendship} layer. Consider the node in the \emph{work} network pointed by a black arrow. This node looks disconnected from the others if we only consider working relations inside the department boundaries. However, it can actually reach the other people in the network in multiple ways. One option is to pass through a common connection outside the department, in this case the grey node on the right. The grey node is external to the department, but on the same layer, connected using the same kind of relations (work). This  represents a case which we call as \emph{horizontally} breaking the network boundary. In a different case, the node can be connected to other people at the department through a connection on a different layer (friend) and thus representing a case which we term as case of \emph{vertical} boundary.

%If we look at the node in the \emph{work} network pointed by a black arrow, it looks disconnected from the others. If we look at the node in the work network pointed by a black arrow and only consider working relations inside the department boundaries, this node is disconnected from the others. However, it can actually reach the other people in the network in multiple ways. One option is to pass through a common connection outside the department, in this case the grey node on the right. The grey node is external to the department but on the same layer, connected using the same kind of relations (work). Therefore we talk of horizontally breaking the network boundary. An another option, the node can be connected to other people at the department through a connection on a different layer (friend). We then talk of vertical boundary.


%However, it can actually be indirectly connected to the group either by staying on the same layer and \emph{horizontally} breaking the network boundary, through a common connection outside the department (the grey node on the right), or by having connections on a different layer, in which case we talk of \emph{vertical} boundary.
%As in a single layer network, network boundary specification can affect the loss of information. However, in addition to putting restriction on the relations and nodes, an experimenter can put additional restriction on layer(s) as well. Also, the censoring of relation and nodes' degree is closely related to the censoring of layer as well.
%
%\textbf{Censoring by vertex degree: }
In addition, a node may have a degree of 100 in the \emph{friendship} layer and 1 in the \emph{work} layer, making it possible for different options of sampling based on degree. We call this specific kind of boundary problem \emph{multidimensional censoring}, e.g., the selection of a subset of objects from the network based on measures computed on multiple layers.%The experimenter has to be careful while performing a censoring process based on neighborhood. It is important to consider a node's combined degree across all the layers.\\
%\noindent
%hen we are on single networks, that have degree 2 but when we move to multi level, deg on 1 in layer 1 and deg 4 in layer 2. Censoring process, neighbourhood, on overall or single layer.
%\textbf{Censoring by Layer: }
%Censoring of a layer might loose some important relations. For example, by not considering any particular layer, such as lunch or Facebook in the above example, can result in considerable amount of loss of information.

%For example, a user A might not be connected to user B directly on LinkedIn (which is more professional) however, A might be connected to B directly on Facebook. Exclusion of any particular network might result in loss of some information. %In terms of dissemination problem this kind of information about relations is vital and thus also establishes the importance of consideration of multi layer networks against single layer networks.
%

%\begin{figure}[t]
%\vspace{-20pt}
%  \begin{center}
%    \subfigure[Multiple dimensions of boundaries]{\label{fig:BB2LDia}\includegraphics[width=0.325\textwidth]{Figures/ML-Dia3.pdf}}
%    \subfigure[Missing data mechanisms]{\label{fig:BB2LCC}\includegraphics[width=0.325\textwidth]{Figures/ML-CC3.pdf}}
%    \subfigure[Average Path Length]{\label{fig:BB2LApl}\includegraphics[width=0.325\textwidth]{Figures/ML-APL3.pdf}}
%    %\subfigure[DBLP]{\label{fig:dblp-md}\includegraphics[width=0.4\textwidth]{DBLP-MesgDism.png}}
%  \end{center}
%  \vspace{-10pt}
%  \caption{Effect of Missing Data in Multiple Layer Network.} \label{fig:MLVarySim}
%  \vspace{-10pt}
%\end{figure}

\begin{figure}[ht]
\begin{center}
   %\subfigure[Multiple dimensions of boundaries]\label{fig:miss-mpx-bound}{\includegraphics[width=0.5\textwidth]{Figures/missing-mpx}}\hspace{.5cm}
   \subfigure[Multiple dimensions of boundaries]{\label{fig:miss-mpx-bound}\includegraphics[width=0.5\textwidth]{missing-mpx.pdf}}\hspace{.5cm}
   %\subfigure[Multiple dimensions of boundaries]{\label{fig:miss-mpx-bound}\includegraphics[width=0.5\textwidth]{missing-mpx.pdf}}\hspace{.5cm}
   \subfigure[Reasons for Missing data\label{fig:miss-mpx-summary}]{%
\begin{tabular}[b]{|l|}\hline
Horizontal boundary specification\\ \hline
Vertical boundary specification\\ \hline
Multidimensional node censoring\\ \hline
Survey non-response (dependent on layer)\\ \hline
Respondent inaccuracy (dependent on layer)\\ \hline
User identity resolution problem\\ \hline
\end{tabular}
}
\caption{Missing data in multiplex networks}\label{fig:miss-mpx}
\end{center}
\end{figure}



\item \emph{Survey non-response} and \emph{respondent inaccuracy} do not significantly change when we move to a multidimensional context, but both can become dependent on the layer under study. For example, people may be less willing to disclose information about their friends than their co-workers, or vice versa. As a result data can be missing from different layers in different ways. If we consider the respondent inaccuracy problem a friendship on Facebook obtained via the Facebook API can be more accurate than an offline friendship collected through a questionnaire. As we will see (in Section \ref{sec:eval}), this is relevant in practice because some layers can reduce the effect of missing data in correlated layers.


%Information about relations is solely dependent on the discreetness of the participants of the study. Depending on the questionnaire this information may not be cross validated. For example, an individual might not divulge its relations with others on Facebook layer by not sharing the Facebook account. Again, this could be due to without any reason or due to some non-divulgence of some relationship status information.
% As in single layer networks, a user might perceive some wrong information about its relations with other individuals present in other networks. For example, based on `co-authorship' layers, a user A might perceive that he is a good friend of B, however B might have a different perception about A.

%a not member of close friends of B and only is connected to B because they are neighbors, however in reality B might perceive A as his good friend. Thus, this kind of cognitive (or assumptions) can lead to loss of some information. For example, an academician A might perceive B as his friend because it has co-authored with B few papers. However, from B's perspective it could be pure professional relation.

\item Multilayer network models also face specific types of missing data that do not exist in simplex networks. If we look again at Figure~\ref{fig:miss-mpx-bound}, we can see that the same nodes are present in the two layers. While this information can sometimes be easily available, e.g., when a single questionnaire is used to collect multiple relational layers, it is often the most challenging part of data to collect from online sources and must sometime rely on uncertain data integration \cite{MagnaniJDIQ10}.
We call this class \emph{user identity resolution problem}. Figure~\ref{fig:miss-mpx-summary} summarises the missing data mechanisms discussed in this section.

\end{enumerate}
%In addition to the above three reasons, non-resolution of user names/IDs on different networks could result in loss of information. Networks such as twitter or email id, provide more freedom in the creation of user ID compared to Facebook. In networks such as Facebook, users can also be identified by profile pictures and other information such as age, school and location, etc. In case a user creates a twitter and email ID by not using his real name, then it could be difficult to resolve two account IDs (from two different networks). Thus, this can lead to inaccurate (or missingness of correct) information in a multilayer networks.




\begin{comment}



From - https://www.princeton.edu/~slynch/soc504/missingdata.pdf
Data are Missing Completely at Random (MCAR)
Data missing on Y are missing at random (MAR)
Data missing on Y are observed at random (OAR) if

%From -- $http://en.wikipedia.org/wiki/Missing_data#Types_of_missing_data$
or
%http://www.upa.pdx.edu/IOA/newsom/semclass/ho_missing.pdf
Generally some reasons are associated behind the missingness of the data.

%When the data is missing not at randomly or in other words for some particular reasons like
. However it is not trivial to find underlying models for the missing data %\cite{%http://www.uvm.edu/~dhowell/StatPages/More_Stuff/Missing_Data/Missing_data2x.pdf}.
1
Not missing at random (NMAR) is data that is missing for a specific reason (i.e. the value of the variable that's missing is related to the reason it's missing).[2] An example of this is if certain question on a questionnaire tend to be skipped deliberately by participants with certain characteristics.


Data are classed as missing not at random (MNAR) if either of the above two
classifications are not met. Thus if the data are not at least MAR, then they are missing
not at random. When data are MNAR there is presumably some model that lies behind
missingness. If we knew that model we might be able to derive appropriate estimators of
the parameters in the model underlying our data. Unfortunately we rarely know what the
missingness model is, and so it is difficult to know how to proceed. In addition,

https://www3.nd.edu/~rwilliam/stats2/l12.pdf

Random versus selective loss of data
Missing by design; or, not asked or not applicable
Many versus few missing data and their pattern. I
\end{comment}



MainFile.bbl
\begin{thebibliography}{10}

\bibitem{Bagrow2013}
J.~P. Bagrow, S.~Desu, M.~R. Frank, N.~Manukyan, L.~Mitchell, A.~Reagan, E.~E.
  Bloedorn, L.~B. Booker, L.~K. Branting, M.~J. Smith, B.~F. Tivnan, C.~M.
  Danforth, P.~S. Dodds, and J.~C. Bongard.
\newblock Shadow networks: Discovering hidden nodes with models of information
  flow.
\newblock {\em CoRR}, 2013.

\bibitem{barabassiModel}
A.-L. Barab\'{a}si and R.~Albert.
\newblock {Emergence of Scaling in Random Networks}.
\newblock {\em Science}, 286(5439):509--512, Oct. 1999.

\bibitem{Bearman2002}
M.~J. S.~K. Bearman, P.~S.
\newblock Chains of affection: The structure of adolescent romantic and sexual
  networks.
\newblock {\em ISERP Working Paper, Columbia University.}, 2002.

\bibitem{Berlingerio2012a}
M.~Berlingerio, M.~Coscia, F.~Giannotti, A.~Monreale, and D.~Pedreschi.
\newblock {Multidimensional networks: foundations of structural analysis}.
\newblock {\em World Wide Web}, Oct. 2012.

\bibitem{Bernard1984}
H.~R. Bernard, P.~Killworth, D.~Kronenfeld, and L.~Sailer.
\newblock {The Problem of Informant Accuracy: The Validity of Retrospective
  Data}.
\newblock {\em Annual Review of Anthropology}, 13(1):495--517, 1984.

\bibitem{Gjoka2011}
M.~Gjoka, M.~Kurant, C.~T. Butts, and A.~Markopoulou.
\newblock {Practical Recommendations on Crawling Online Social Networks}.
\newblock {\em IEEE J. Sel. Areas Commun. on Measurement of Internet
  Topologies}, 29(9):1872--1892, 2011.

\bibitem{Kivela2014}
M.~Kivela, A.~Arenas, M.~Barthelemy, J.~P. Gleeson, Y.~Moreno, and M.~A.
  Porter.
\newblock Multilayer networks.
\newblock {\em arXiv}, 2014.

\bibitem{Kossinets_SocNet2005}
G.~Kossinets.
\newblock {Effects of missing data in social networks}.
\newblock {\em Social Networks}, 28(3):247--268, July 2006.

\bibitem{lauman}
E.~O. Laumann, P.~V. Marsden, and D.~Prensky.
\newblock {\em {The boundary specification problem in network analysis..}},
  pages 18--34.
\newblock Sage Publications, London, 1983.

\bibitem{Leskovec2006}
J.~Leskovec and C.~Faloutsos.
\newblock {Sampling from large graphs}.
\newblock In {\em Proceedings of the ACM SIGKDD conference on Knowledge
  discovery and data mining}, pages 631--636, 2006.

\bibitem{LittleAndRubin}
Little and Rubin.
\newblock Statistical analysis of missing data.

\bibitem{Magnani2013}
M.~Magnani, B.~Micenkov{\'a}, and L.~Rossi.
\newblock Combinatorial analysis of multiple networks.
\newblock {\em CoRR}, abs/1303.4986, 2013.

\bibitem{MagnaniJDIQ10}
M.~Magnani and D.~Montesi.
\newblock {A Survey on Uncertainty Management in Data Integration}.
\newblock {\em ACM Journal of Data and Information Quality}, 2010.

\bibitem{magnani2013formation}
M.~Magnani and L.~Rossi.
\newblock {Formation of multiple networks}.
\newblock In {\em Social Computing, Behavioral-Cultural Modeling and
  Prediction}, pages 257--264. Springer Berlin Heidelberg, 2013.

\bibitem{MatteoMuldiDimNw}
M.~A. R. G. G.~F. Magnani, M.
\newblock On multidimensional network measures.
\newblock In {\em Italian Conference on Sistemi Evoluti per le Basi di Dati
  (SEBD)}, 2013.

\bibitem{Marsden1990}
P.~V. Marsden.
\newblock {\em {Network data and measurement.s}}, pages 435--463.
\newblock 1990.

\bibitem{Roethlisberger1939}
D.~W.~J. Roethlisberger, F.~J.
\newblock Management and the worker.
\newblock {\em Harvard University Press, Cambridge, MA}, 1939.

\bibitem{Rumsey1993}
D.~J. Rumsey.
\newblock Nonresponse models for social network stochastic processes (markov
  chains).
\newblock 1993.

\bibitem{Sadikov2011}
E.~Sadikov, M.~Medina, J.~Leskovec, and H.~Garcia-Molina.
\newblock Correcting for missing data in information cascades.
\newblock In {\em Proceedings of the Fourth ACM International Conference on Web
  Search and Data Mining}, WSDM '11, pages 55--64, New York, NY, USA, 2011.
  ACM.

\bibitem{Salehi2013}
M.~Salehi and H.~R. Rabiee.
\newblock A measurement framework for directed networks.
\newblock {\em IEEE Journal on Selected Areas in Communications (JSAC): Special
  Issue on Network Science}, 31(6):1007--1016, 2013.

\bibitem{Travers69anexperimental}
J.~Travers and S.~Milgram.
\newblock An experimental study of the small world problem.
\newblock {\em Psychology Today}, 2:60--67, 1967.

\end{thebibliography}
