# Online Social Space Identification. A Computational Tool for Optimizing Social Recommendations
## 3 The \"Social Space Identification\" Problem
### Main Notation and Definitions  
Graphs are abstract models of complex relationships commonly established in current networks. Formally, a graph \(G=(V,E)\) is a collection of the network's entities (i.e., vertices, \(V\)) and interactions among them (edges, \(E\)). Given a graph \(G\), we use the corresponding adjacency matrix \(A\), which indicates whether two vertices \(v_{i},v_{j}\) of \(G\) are connected by an edge, i.e., \((A)_{i,j}=1\), if \(\{v_{i},v_{j}\}\in E\). We also use the notation \(A[i,k:j,m]\) to denote the sub-matrix of \(A\) indexed by the rows \(i...k\) and columns \(j...m\). Moreover, we denote by \(G[V^{\prime}]\) the subgraph of \(G\) induced by the subset of vertices \(V^{\prime}\in V\). A path in \(G\) is a finite (or infinite) sequence of edges that joins a sequence of distinct vertices. The distance, \(d_{G}(u,v)\), between two distinct vertices \(u\) and \(v\) is the number of edges in the shortest path connecting them. The diameter of \(G=(V,E)\) is defined as \(\max_{u,v\in V}d_{G}(u,v)\), i.e., the maximum distance between any two vertices in \(V\). Finally, we denote by \(N(v)=\{u:\{v,u\}\in E\}\) the neighborhood of a vertex \(v\). The following definitions are fundamental for our objectives:  
**Definition 1**. : _Two-clubs are subgraphs where all the vertices are at a distance at most two. Importantly, given a graph \(G=(V,E)\), a two-club in \(G\) is a subgraph \(G[W]\), with \(W\subseteq V\), whose diameter is at most equal to two._  
Let \(G\) be a graph, \(V=T\cup X\cup R\) its set of vertices, and \(T\), \(X\), and \(R\) the set of RD patients, EX patients, and HSP centers, respectively. Consider a labeling function \(h:V\to S\) that assigns to each vertex in \(V\) a (type of) service in \(S\). Notice that a service \(h(v)\in S\) can be required by new users \(v\in T\) (e.g., \(v\) requires information about \(h(v)\)), already prescribed for some expert \(v\in X\) (e.g., \(v\) was followed up with \(h(v)\)) or available in some center \(v\in R\) (i.e., health service \(h(v)\) is available in \(v\)). **Definition 2**. : _A vertex \(x\in X\), for which there exists, in \(N(x)\), at least one pair \((t,r)\in T\times R\), where \(h(t)=h(x)=h(r)\), will be named a \"feasible vertex\". Moreover, we call the set of \"feasible vertices\", \(\mathcal{C}\), a \"feasible set\" and the pair, \((t,r)\), a feasible pair._  
In our example, feasible vertices are experts \"equipped\" with pairs \((t,r)\) consisting of a new patient \(t\) with the available caregiver \(r\). In other terms, when a new (target) patient \(\hat{t}\) requires information, our interest will be to supply \(\hat{t}\) with his/her \"own\" heterogeneous community of users/items \(G[T^{\prime}\cup X^{\prime}\cup R^{\prime}]\), with \(T^{\prime}\subseteq T\), \(X^{\prime}\subseteq X,R^{\prime}\subseteq R\), consisting of the largest number of feasible pairs. More formally, we seek a maximum size two-club for \(\hat{t}\) (i.e., \(\hat{t}\) included), which has the further property of providing, the largest number of (feasible) pairs \((t,r)\) whose vertices \(t\) and \(r\) are connected with at least one simple path passing through some \(x\in X^{\prime}\), such that \(h(\hat{t})=h(x)=h(r)\), i.e., the information about service \(h(\hat{t})\), requested by \(\hat{t}\), is available with (the caregiver) \(r\). This information can be obtained consulting \(x\)For any \"target\", the identification of the largest size two-club (with the largest number of feasible pairs) offers multiple sources of alternative information (each node of a two-club community being reachable through paths of size two). In other words, \"targets\" can acquire greater awareness in reaching available resources by exploiting different paths and through different \"experts\". For example, in our case, recent patients (i.e., target users) can collect information on alternative providers (HSP) from the same expert, as well as information on the same center from different available experts.