## 4 Detailed Design
### Social Tie Classifier System
#### 4.1.2 Nodes' Friends Discovering Mechanism  
After discovering the nodes' acquaintanceship, the social tie classifier system discovers the nodes' friends. To obtain this information, our system takes into account two scenarios: (i) the information about the friendship strength between the nodes is available (self-reported friendship), and (ii) the self-reported information is not available. In scenario (i), every node only loads this information in its _my social ties_ list. This information can be found in some datasets derived from real experiments. For example, in the Reality Mining experiment [9], the authors provided to the scientific community diverse information from the users, including the self-reported friendship among them. Figure 3 shows the friendship graph used by FSF in the Sassy scenario [11]. In scenario (ii), the social tie classifier system uses a _machine learning scheme_ to discover the existence of friendship between each pair of nodes in the network. This scheme is composed of a classifier algorithm and a database used for training the classifier. The classifier used is the Naive Bayes classifier [41]. We choose this classifier based on our previous works [35; 42], where it achieved promising performance. The Naive Bayes classifier uses the Bayes' theorem to calculate the probabilities necessary to classify a new instance. From a machine learning perspective, we can define the [PERSON] theorem as follows: given an unknown instance \(A=(a_{1},...a_{n})\), where \(a_{i}\) is one of the values of \(A\), we wish to predict to which class \(A\) belongs. According to [PERSON] theorem, the probability of choosing a class given a sample is given by:  
\[P(Class|A)=\frac{P(Class|A)\times P(Class)}{P(A)}. \tag{5}\]  
We can rewrite Equation (5) in terms of the attributes of instance A:  
\[P(Class|A)=\frac{P(Class|a_{1},...,a_{n})\times P(Class)}{P(a_{1},...,a_{n})}. \tag{6}\] \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Trace** & _Cambridge_ & _Reality_ & _NCCU_ & _Sassy_ \\ \hline
**Device** & iMotes & Phone & Smart Handheld & T-mote \\
**Network Interface** & Bluetooth & Bluetooth & Wi-fi/Dusteoth & Sensor \\
**Nodes** & 54 & 97 & 115 & 27 \\
**Trace Duration** (days) & 11 & 246 & 15 & 79 \\
**Number of contacts** (approx.) & 10.873 & 54.667 & 81.115 & 35.274 \\
**T value** (days) & 3 & 7 & 3 & 7 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Parameters describing the traces used in the simulation. The class definition of instance A involves the computation of the probability for all possible classes given a particular attribute. The defined class is the one with the highest probability. From a statistical perspective, this is equivalent to maximizing P(Class \(\mid\!a_{1}\), Class \(\mid\!a_{2}\),..., Class \(\mid\!a_{n}\)). The denominator in Equation (6) is constant, which leads to the following simplification:  
\[P(Class|A)=argmax\ (P(Class|A)\times\prod_{i}P(Class|a_{1},...a_{n})). \tag{7}\]  
To build the database used for training and testing the Naive Bayes classifier, we took advantage of data derived from the MIT research experiment [9]. In this experiment, the data were taken from a test with mobile devices equipped with a Bluetooth network interface. The experiment collected data from 97 mobile phones over the course of six months. We can have access to information related to connectivity, proximity, location, and activities of these users. Additionally, by answering the question \"Is this person part of your close circle of friends?\", users assigned to which other people participating in the experiment they have a friendship relationship. Then, we built a database combining this self-reported friendship information with other attributes related to the users' history of meetings. In this way, this database is composed of the following attributes and their possible values:  
* **Number of meetings (NM)--**Represents how many times two nodes were within the radio range of each other. Possible values: low, average, and high.