
% In this Section, we go into details of our temporal-based user bias classification algorithm. Table~\ref{tab:notation} gives the main
% symbols used in this paper. We assume we are given a set of users, $U_{known}$, whose class is previously known,
% and the goal of the algorithm is to compute $B_{u,w}$ for all $u \in U_{unknown}$, i.e., the bias of user $u$ towards each class $w$.
% Each class represent a side a user can position himself with respect to a topic. $W=\{Democrat,Republican\}$ and $W=\{Flamengo,Vasco,Botafogo,Fluminense\}$
% are possible sets of classes. We also assume that timestamps of users posts are available. We then discretize timestamps into a chronological ordered set of time units $T$, each set $T_i$ stores all users that posted at time unity $i$. Since our assumption is that users belonging to the same class are likely to post at moments which are close, we expect that users who posted in the same time unity are more likely to belong to the same class.

% \begin{table}[ht]
% %  \setlength\abovecaptionskip{0pt}
% %  \setlength\belowcaptionskip{6pt}
%   \begin{footnotesize}
%     \begin{center}
%       \caption{Symbols}
% \begin{tabular}{|c|c|} \hline
%   \textbf{Symbol} & \textbf{Description}  \\\hline
%   $U_{known}$ & vector representing users whose class is known     \\\hline
%   $U_{unknown}$& vector representing users whose class is unknown   \\\hline
%   $T_{i}$ &  contains all users that posted within time unit $i$     \\\hline
%   $W$ & vector containing all classes \\\hline
%   $B_{u,w}$ & measure of class membership of user $u$ towards class $w$ \\\hline
%   $N_w$ & membership of neutral user to class $w$ \\\hline
  
%  % number of users  & 9,323,883     \\\hline
    
% \end{tabular}
% \vspace {-5pt}
% \label{tab:notation}
% \end{center}
% \end{footnotesize}
% \end{table}

% The algorithm process users posts in chronological order, as stated on the outermost loop (line 3).
% Line 3 checks if the current time unity accumulated a minimum number of posts to be taken into account -- the effect
% of that parameter will be discussed in Section~\ref{sec:results}. For each $T_i$, the loop in lines 6--8 computes  the membership 
% class vector $v$, whose dimensionality is $|W|$ (the number of classes) and each $v_w$ accumulates the
% number of posts of users who belong to class $w$ who posted on that time unity (line 7). This is the training phase of our classification algorithm, which learns
% from previously ground thruth information. 

% To predict the bias of new users, the loop from lines 10--12
% adds the characteristic vector $v$ which has just been computed to the bias vector $B_u$ of all
% users of unkown bias who had posted messages in time unity $i$. At line 15, all time intervals
% have been processed and $B_{u_w}$ contains a quantification of the bias of user $u$ towards class $w$,
% which is simply the number of users from that class which posted in the same time intervals as him
% over all the time period being considered. We then predict the class of user $u$ is thus simply $w = argmax(B_{u,w})$.

% %At the end of the call, $U$ contains the users who wrote during the
% %current ``pick'' (until now), $v$ is its characteristic vector
% %(therefore its dimensionality is the number of classes), $d$ indicates
% %whether the current trend is the decrease of the number of tweets
% %(Boolean value) and $M$ maps all users with their current
% %characteristic vector. 

% % \algsetup{
% % linenosize=\small,
% % linenodelimiter=.
% % }
% % \begin{algorithm}{LEARN\_USER\_BIAS($postsPerTimeIntervalThreshold$, $U_{known}$)}
% %   \begin{algorithmic}[1]
% %    % \STATE \textbf{Input:} $n_{\text{previous}}$, the number of tweets
% %    % at the previous iteration, $T_{\text{current}}$ the tweets
% %    % collected since the previous iteration, $U_{\text{current}}$ the
% %    % users who wrote these tweets.
% %    \STATE \textbf{Input:} $postsPerTimeIntervalThreshold$, the minimum number of posts required to consider the time interval,
% %    $U_{known}$, a set of users whose class is previously known (training set)
% %    \STATE \textbf{Output:} $B_{u,w}$, the strength of user $u$ towards class $w$.
	
% % 	 \FOR{$i=0$ to $numTimeUnits$}
% % 	 \IF{$|T_i| \geq postsPerTimeIntervalThreshold$}

% %  %  \FORALL{$u \in T_{i} \wedge u \in U_{known} $}
% %       \STATE $v \leftarrow (0, \dots, 0)$
% % 	  \FORALL{$w \in W$}
% % 	      \STATE $v_w \leftarrow $\texttt{count}$(w,T_i \cap U_{known} ) $
% % 	   \ENDFOR
% %  %  \ENDFOR
% %     \ENDIF
   
   
% %    \FORALL{$u \in U_{unknown} \cap u \in T_{i} $}
% %    			\STATE $B_{u,w} \leftarrow B_{u,w} +  v_w $
% %    \ENDFOR
% %    \STATE $N_{w} \leftarrow N_{u,w} +  v_w $
% % %    \IF{$u \in U_known$}

% %     \ENDFOR % fim do loop de tempo
    
% %      \FORALL{$u \in U_{unknown} $}
% %      		\FORALL{$w \in W$}  
% % 		  \STATE $B_{u,w} \leftarrow B_{u,w} / N_w$
% % 		     \ENDFOR

% %      \ENDFOR
    
% % \end{algorithmic}
% % \caption{Temporal Locality User Bias Classification}  
% % \end{algorithm}

% \algsetup{
% linenosize=\small,
% linenodelimiter=.
% }
% \begin{algorithm}{LEARN\_USER\_BIAS($postsPerTimeIntervalThreshold$, $U_{known}$)}
%   \begin{algorithmic}[1]
%    % \STATE \textbf{Input:} $n_{\text{previous}}$, the number of tweets
%    % at the previous iteration, $T_{\text{current}}$ the tweets
%    % collected since the previous iteration, $U_{\text{current}}$ the
%    % users who wrote these tweets.
%    \STATE \textbf{Input:} $postsPerTimeIntervalThreshold$, the minimum number of posts required to consider the time interval,
%    $U_{known}$, a set of users whose class is previously known (training set)
%    \STATE \textbf{Output:} $B_{u,w}$, the strength of user $u$ towards class $w$.
	
% 	 \FOR{$i=0$ to $numTimeUnits$}
% 	 \IF{$|T_i| \geq postsPerTimeIntervalThreshold$}

%  %  \FORALL{$u \in T_{i} \wedge u \in U_{known} $}
%       \STATE $v \leftarrow (0, \dots, 0)$
% 	  \FORALL{$w \in W$}
% 	      \STATE $v_w \leftarrow $\texttt{count}$(w,T_i \cap U_{known} ) $
% 	   \ENDFOR
%  %  \ENDFOR
%     \ENDIF
   
   
%    \FORALL{$u \in U_{unknown} \cap u \in T_{i} $}
%    			\STATE $B_{u,w} \leftarrow B_{u,w} +  v_w $
%    \ENDFOR
%    \STATE $N_{w} \leftarrow N_{u,w} +  v_w $
% %    \IF{$u \in U_known$}

%     \ENDFOR % fim do loop de tempo
    
%      \FORALL{$u \in U_{unknown} $}
%      		\FORALL{$w \in W$}  
% 		  \STATE $B_{u,w} \leftarrow B_{u,w} / N_w$
% 		     \ENDFOR

%      \ENDFOR
    
% \end{algorithmic}
% \caption{Temporal Locality User Bias Classification}  
% \end{algorithm}

% A major drawback of this algorithm is that it
% is clearly sensitive to class imbalance, a
% known problem in classification which
% occurs in many real-world applications where the class distributions of data are highly imbalanced~\cite{costSensitive}.
% Class imbalacemnt can potentially occur in our scenario, since some classes (think of supporters or Flamengo or Corinthians, for example),
% can be far superior in number of users than others. To tackle this problem, we normalize each bias vector in relation to a hypothetical user -- the \emph{neutral user} -- who posted in \emph{all} time intervals, and thus he is not influenced by real life events in order to take the decision to post.
% The bias vector of the neutral user is computed in line 13. In lines 15--19, we normalize all user vectors in relation to the neutral user vector.

% Note that our user bias classification algorithm exhibits the following features:

% \begin{itemize}

% \item it classifies social media users based solely on the timestamp of their posts;

% \item it has linear complexity in number of instances (users) and number of time intervals, what makes it quick
% and suitable for large-scale mining of social media usage data;

% \item it is naturally incremental and thus suitable for real-time mining of social media user data.

% \end{itemize}

% \pcalais{DAR UM RUNNING EXAMPLE VALE A PENA?}

In this section we present our proposal for addressing the problem
of determining the user bias based on temporal information.

\subsection{Architecture of the Approach}

Figure~\ref{fig:architecture} depicts the architecture of our
approach. Microblogging platforms such as Twitter have an API that
allows to collect the messages based on the presence of keywords in
their content. However, once outside the microblogging platform, our
approach completely disregards the content of the messages. That is
why, in the remainder of this paper, the word ``message'' only stands
for the time it was sent and its author. In
Figure~\ref{fig:architecture}, every rectangle represents a separate
process. Those processes read their input (plain arrow from the source
to the reader) and write their output (dotted arrow from the writer to
the destination) in either a buffer (dotted ellipse) or a database
(plain ellipse).

\begin{figure}
  \centering
  \includegraphics[width=.75\linewidth]{figures/architecture}
  \caption{The stream of messages, from the microblogging platform, is
    divided into time intervals. In each time interval, the users with
    known biases are used to learn more about the biases of all users
    in the same interval. A separate process takes care of the needed
    normalization that remains to be done when a specific user bias is
    queried.}
  \label{fig:architecture}
\end{figure}

The remainder of this section presents the successive processes:
\begin{itemize}
\item the selection of time intervals that leads to grouping the
  messages;
\item the supervised learning of users' biases, which is the core of
  our contribution;
\item the normalization of a bias performed when that of a user is
  queried.
\end{itemize}

\subsection{Selection of Time Intervals}

Our approach assumes that users having similar biases are prone to
send messages at about the same time. To clearly show that this
assumption holds, the experimental section of this paper relies on a
very simple method to temporally group the messages: a fixed duration
is chosen and the whole stream is binned accordingly (without any
overlap of the time intervals). Nevertheless, it is interesting to
point out that more sophisticated methods may lead to better
results. For example, since the synchronicity of the users' expression
is explained by events that trigger them, one could try to detect
these events. Intuitively, they should correspond to ``peaks'' of
activity. Detecting those peaks in the stream of messages is an
interesting topic and known algorithms (\eg, \cite{PeakDetection})
that analyze time-series data can perform this task. The temporal
basis of the peaks would then define intervals in which messages are
grouped. Weighting the subsequent learning step with the salience of
these peaks may also improve the results. However, the main goal of
this paper is to stress the mere existence of a temporal ``pattern''
that allows to efficiently learn the biases of the users. This goal
would be weakened by the many parameters required to configure a peak
detection algorithm. That is why the investigation of more
sophisticated definitions of the time intervals is left as future
work. Notice however that Section~\ref{sec:min_size} shows that better
precisions are achieved by discarding the time intervals with too few
messages.

\subsection{Supervised Learning of Users' Biases}

\subsubsection{Defining Known Biases}

Let $\mathcal{C}$ be a set of classes. For example, $\mathcal{C} =
\{$democrat, republican, green$\}$ could be used to learn political
biases of American users of a microblogging platform. We represent bias as a
vector of $|\mathcal{C}|$ positive values. Those values are higher
when they relate to classes the user is biased toward. The considered
setting is that of supervised learning, \ie, an associative array,
$B_{\text{known}}$, is defined beforehand and relates the users' IDs
to their known biases. These biases may be characteristic vectors,
\ie, they may contain one value that equals to 1 while all remaining
values are 0. For instance, known politicians' biases could be at 1
for their party and 0 for the other parties. However, these vectors
must not necessarily be so. For instance, a democrat senator who is
known to be close to the ideas of the green party may be considered
known and her bias defined (in $B_{\text{known}}$) as $(0.6, 0, 0.4)$,
where the first and third values respectively relate to the democrat
and the green class. The norm of the known biases must not necessarily
be the same either. In this way, the analyst can encode the certainty
of the known biases.

A way to automatically define the known biases is to look at the
content of a fixed subset of messages (by opposition to working on the
stream). For example, each class can be associated with some terms
that its members frequently use (\eg, the mere name of the class). By
counting, for each user, the number of occurrences of the words
associated with each class, one can assume that the users writing a
lot of such words (threshold to fix) is known and her bias is the
vector of the counts of words. This step is computationally demanding
since the content must be read. However, it does not need to be
performed on a huge quantity of messages and is separated from the
actual learning algorithm, which processes the stream of messages
without reading them.

The biases of the most vocal users are expected to be durable
measures. As a consequence, $B_{\text{known}}$ can be defined once for
all. However, and depending on the application, this durability may
have some limits. For example, a political partisan may, after some
years, move to another party. That is why it makes sense to update
$B_{\text{known}}$ from time to time. This update does not require to
stop the learning process presented in the next
section. Furthermore the learning process also learns the bias of the
known users (but does \emph{not} modify $B_{\text{known}}$). As a
consequence, an increasing dissimilarity between the learned vector
and that in $B_{\text{known}}$ could be used to indicate when a
supposedly known bias becomes inaccurate.

\subsubsection{Algorithm}

Algorithm~\ref{alg:learn} details how (absolute) biases are
learned. It reads that from a stream of messages and group them in
intervals (if the buffer is empty, it waits for one). The multiset $U$
contains all users which posted a message during that interval. $U$ is
a multiset because users can post more than once in a same
interval. For instance, $\{U_1, U_1, U_2, U_3\}$ is a multiset in
which the user $U_1$ posted twice. For every group $U$,
Algorithm~\ref{alg:learn} processes the messages in two steps. First
of all, it learns, from the presence of known users, what is the bias
$V$ of the group of messages. Then, every user $u$ in the group has
its bias $B[u]$ updated w.r.t. the group bias $V$.

\begin{algorithm}
  \begin{algorithmic}
    \STATE $S \leftarrow (0, \dots, 0)$
    \WHILE{\textbf{true}}
    \STATE $U \leftarrow$ \textsc{getUsersInAGroup}$()$
    \STATE $k \leftarrow 0$
    \STATE $V \leftarrow (0, \dots, 0)$
    \FORALL{$u \in U$}
    \IF{$u$ is a key of $B_{\text{known}}$}
    \STATE $V \leftarrow V + B_{\text{known}}[u]$
    \STATE $k \leftarrow k + 1$
    \ENDIF
    \ENDFOR
    \STATE $S \leftarrow S + k.V$
    \FORALL{$u \in U$}
    \STATE $B[u] \leftarrow B[u] + V$
    \ENDFOR
    \ENDWHILE
  \end{algorithmic}
  \caption{Learning biases by temporal locality.}
  \label{alg:learn}
\end{algorithm}

For each interval, the biases \emph{learned} for all $k$ known users
is computed. The idea is here to quantify the bias of the whole
microblogging system (restricted to the known users as always with
supervised learning) during the interval. Summing these vectors,
interval after interval, in the global variable $S$, therefore gives
the bias of the microblogging system for the whole stream of messages
until the current interval. It is useful to compute a normalized bias
when queried. Section~\ref{sec:bias} details this process and
clarifies why this computation for $S$ makes sense.

$B$ is a global variable too. It is an associative array (initially
empty) that associates each user with her absolute bias. Again, it
will be explained later why the desired biases are not directly those
absolute vectors but a relative version taking into account the
overall bias $S$. To expose the pseudo-code in the simplest possible
way, $B[u]$ is assumed to be the null vector when $u$'s first message
is processed.

\subsubsection{Complexity Analysis}

During the iterative computation of the vector $V$ (the bias of the
processed group of users), the associative array $B_{\text{known}}$ is
accessed $|U|$ times. Each of these accesses has a constant time
complexity. Indeed, $B_{\text{known}}$ being unaltered after its
creation, any of its values can be accessed through a perfect hash
function. As a consequence, in the worst case ($U$ only contains users
with known biases), this step has a $O(|U|.|\mathcal{C}|)$ time
complexity.

During the update of users' biases, the associative array $B$ is also
accessed $|U|$ times but, this time, new users are inserted. As a
consequence, by implementing $B$ as a hash map, access and insertion
operations may suffer from possible hash
collisions~\cite{AlgorithmDesignManual}. In the worst case (all
entries in the same bucket), the complexity of this step would be
$O(|U|.(|B| + |\mathcal{C}|))$. However the amortized complexity only
is $O(|U|.|\mathcal{C}|)$. In a real-time context (where only the
worst case scenario matters), it is preferable to access and insert
the content of $B$ through a self-balancing binary tree. The cost of
one of these operations becomes $O(\log(|B|))$, hence an overall time
complexity of $O(|U|.(\log(|B|) + |\mathcal{C}|))$ for processing a
given group of messages (the complexity of the first step being
negligible). This computational cost is far smaller than those of the
approaches based on the content (our approach completely disregards
it) or those exploring a graph of users.

Since there may be a lot of users (memory management), since their
biases should not be lost in case of failure (durability), since the
querying process must access these biases (isolation) and for the
other assurances brought by the respect of the ACID
principles~\cite{ACID}, $B$, $B_{\text{known}}$ and $S$ are stored in
database tables with the indexes chosen as explained above. The space
to store these variables is $O((|B| +
|B_{\text{known}}|).|\mathcal{C}|)$.

\subsection{Querying Biases}

\subsubsection{User Bias}
\label{sec:bias}

Given a user $u$, $B[u]$ is her absolute bias. Alone, this information
is not that valuable. Indeed, it is computed from the simultaneous
expression with known users whose total quantities of messages may not
be balanced, \ie, some opinions may be over-expressed (in particular
if the repartition of the known users is not that of the classes). For
example, in the American political context, $B_{\text{known}}$ may
globally be biased towards a party and, furthermore, the known users
biased toward this party may be more vocal, \ie, write more
messages. Only looking at the absolute biases would overestimate the
support of the users to this party, a problem known in machine
learning theory as class imbalancement~\cite{costSensitive}.

To avoid this pitfall, every class is supposed to globally have the
same weight. More precisely, the absolute bias (in $B$) is normalized
so that the sum of the normalized biases of every known user is the
vector $(1, \dots, 1)$. Algorithm~\ref{alg:bias} does so. It divides
every component of a user absolute bias by the sum of the respective
component over all known users. These sums actually are the vector $S$
computed by Algorithm~\ref{alg:learn}, \ie, the overall absolute bias
of the known microbloggers. Notice that the normalization is performed
when querying the user biases. Normalizing the database would be less
efficient unless the bias of the average user is queried more than
once per interval. Indeed, directly storing the normalized biases
would require an update of every entry at every time interval because
$S$ is updated with this frequency.

\begin{algorithm}
  \begin{algorithmic}
    \STATE \textbf{Input:} a user $u$.
    \STATE \textbf{return} $\Big(\frac{B[u]_1}{S_1}, \dots,
    \frac{B[u]_{|\mathcal{C}|}}{S_{|\mathcal{C}|}}\Big)$
  \end{algorithmic}
  \caption{User bias.}
  \label{alg:bias}
\end{algorithm}

The components of a normalized bias are proportions. Therefore, the
orientation of a vector is to be understood in a relative way. For
example, in a political context, a user commenting a few live
declarations from a minor party (in the sense that these declarations
do not draw many messages on the microblogging platform) may have a
strong normalized bias towards this party even though she commented as
well many more declarations from a major party (but fewer in terms of
proportion of the generated ``buzz''). Another interesting observation
is that the absolute bias carries useful information too: each of its
components quantifies the certainty of the orientation (given by the
normalized bias) towards the related class. The larger (\ie, the more
messages from known users having a bias towards this class and
expressing themselves at the same time as the assessed user), the more
certain.

\subsubsection{Overall Bias Along Time}

In Algorithm~\ref{alg:learn}, the vector $V$ gives the absolute bias
of the group of messages that is currently processed. This vector can
be normalized in the way described in
Section~\ref{sec:bias}. Observing it across time allows to have a
glance at the evolution of the bias of the microblogging platform as a
whole. In a near future, we plan to implement this idea within the
``Observat\'orio da Web\footnote{www.observatorio.inweb.org.br}'', a
system that gathers, processes and presents aggregated data collected
in blogs, microblogs, and news media sites.

\subsubsection{Running Example}

This section illustrates our algorithm on a small example. Assume
three classes (A, B and C) and users that have known biases toward one
class only. More precisely these users have, in $B_{\text{known}}$, 1
for the class they are biased toward and 0 for the other classes. The
goal is the prediction of the (normalized) bias of a user X using the
co-occurrence (\ie, the occurrence in the same intervals) of her
messages with those of the known users. Table~\ref{tab:example} lists
all relevant information of a hypothetical stream of data until the
time when the query is received. More precisely, the second column
indicates whether $X$ posted during an interval, $V$ is the bias of an
interval, and $k$ is the number of messages from known users in an
interval. Because, in this example, every known bias has a component
at 1 and the other components at $0$, $k$ actually is the 1-norm of
$V$, \ie, $k = \sum_{i = 1}^3 V_i$.

\begin{table*}
%  \setlength\abovecaptionskip{0pt}
%  \setlength\belowcaptionskip{6pt}
  \begin{footnotesize}
    \begin{center}
      \caption{Hypothetical dataset of users from classes A, B and C posting messages in reaction to live events.}
      \begin{tabular}{|c|c|c|c|c|} \hline
        \textbf{interval} & \textbf{post from user X?} & \textbf{$k$} & \textbf{$V$} & $k.V$ \\\hline
        1 & yes & 750 & [A = 500, B = 200, C = 50] & [A=375,000 B=150,000 C=37,500] \\\hline
        2 & no & 180 & [A = 100, B = 50, C = 30] & [A=18,000 B=9,000 C=5,400] \\\hline
        3 & yes & 30 & [A = 10, B = 10, C = 10] &  [A=300 B=300 C=300] \\\hline
        4 & no & 70 &  [A = 10, B = 50, C = 10] & [A=700 B=3,500 C=700] \\\hline
        5 & yes & 300 & [A = 200, B = 0, C = 100] & [A=60,000 B=0 C=30,000] \\\hline
        6 & no & 250 & [A = 100, B = 100, C = 250]  & [A=25,000 B=25,000 C=62,500] \\\hline
        7 & no & 1000 & [A = 50,B = 50,C = 900] & [A=50,000 B=50,000 C=900,000] \\\hline
      \end{tabular}
      % \vspace {-5pt}
      \label{tab:example}
    \end{center}
  \end{footnotesize}
\end{table*}

If we run Algorithm~\ref{alg:learn} over Table~\ref{tab:example},
we will get $B[X] = [A=710, B=210, C=160]$, which is the sum of the
number of times members of each class manifested in intervals in
which user X also posted a message (intervals 1, 3 and 5). Algorithm 1
also computes $S=[A=375,000+18,000+300+700+60,000+25,000+50,000=592,000, B=150,000+9,000+300+3,500+30,000+25,000+50,000=237,800, C=37,500+5,400+300+700+30,000+62,500+900,000=1,036,400]$, which is the bias 
of the whole system. We then apply Algorithm 2 to neutralize the effect
of some classes being more intense than others in the system (for example,
class A may have more adopters, and thus, any computation of bias will tend
to favor A) and our estimation of bias of user X based on the moment he
posts messages is $B[X]=[A=0.0012, B=0.0008, C=0.0001]$.

Thus, our algorithm predicts that X should be inclined to support class A.
Note that this is expected since user X posted on a time interval (interval 1)
in which we observed a high fraction of posts from users belonging to class A,
what indicates that some event on the real world (a goal from a team, for example)
just took place and caused reactions from members of that class. On the other hand,
user X did not manifest at interval 7, which is clearly an interval which attracted
comments from class C. The result is that our algorithm predicted a very low probability
of user X belonging to class C.
