Community-Based User Domain Model Collaborative Recommendation Algorithm

Real-world social networks often exhibit a strong community structure^{[ 16 ]}. A community is usually considered as a group of users whose members interact with others more frequently than with those outside the group. Users in the same communities are frequently connected, and thus probably have similar tastes and interests. In a social network, these communities often yield better recommendation results.

Based on the above motivation, we propose the CUCRA algorithm implemented in two parts: the first part is building the offline user domain model; the second part is recommending items to target users in the model.

The more important part is the former, that is, the community-based user domain model generation method. The generation method follows three steps: (1) Calculate user similarities using a user-item preference dataset; (2) map the similarity relationships to user-user social network relationships; (3) apply an existing community detection method to generate communities as user domains.

In the second step, we define a $K$ -nearest neighbor graph $G_K=(V;E_K)$ as a user-user social network where $V$ is the set of users, and $E_K$ is the set of edges. According to the KNN strategy, for each user, compute the top- $K$ largest similarity users, and establish edges between each two users. In cases where there are many edges between two users, only a single edge is kept. We map the user-item data relationship to the user-user network relationship through the above method. The intrinsic mechanism is mining user social behavior through user-item rating behavior. This mining process is described in Fig. 1 .

10.1109/TST.2013.6574673.F001 Fig. 1(a) User-item relationship; (b) User-user social network. The black spots represent users and the white spots represent items. The figure shows how the user-item relationship is mapped to the user-user social network.

Building the model consumes offline time; next, we analyze the time complexity of Algorithm 1. We calculate the similarity between any two users according to the rating of items in Phase 1, so the minimum time cost is $O(m^{2}n)$ . We then determine the top- $K$ largest similarity users of the target user in Phase 2. The essence of the algorithm is sorting, and the time-complexity of sort algorithms is $O(m\log n)$ . There are various community detection algorithms and the most well-known and mature algorithm is the Gauss-Newton (GN) algorithm, the detection algorithm used in this version of CUCRA. Other algorithms include the Newman fast algorithm, PLA, and modifications of these, algorithms. The maximum time complexity of community detection algorithms is $O(m^3)$ , such as GN, while minimum time complexity is $O(m^2)$ such as PLA. Because the whole time complexity of an algorithm is determined by the maximum value of every phase. Thus, time complexity in building a user domain model is $O(m^3)$

After building the user domain model, we recommend items of interest to a target user in a community. The formula to compute prediction is defined by Eq. ( 1 ).

(1) $${\tilde{r}}_{i\alpha }={\bar{r}}_i+\frac{1}{{\sum }_v|S_{ij}|}\underset{j\in \text{Ucom}(i)}{\sum }{S}_{ij}(r_{j\alpha }-{\bar{r}}_j)$$

$\text{Ucom}(i)$ denotes the set of users in the same community as user $i$ , $S_{ij}$ represents the similarity between user $i$ and user $j$ , and $r_{j\alpha }$ is the rating of user $j$ for item $\alpha$ .

In the online phase, which is described by Algorithm 2, because the similarity relation has already been calculated for the target users, we only need to find common rating items within the community of $m^{\prime }$ users. Online time complexity is $O(m^{\prime }n)$ , and $m^{\prime }$ is far less than $n$ , so online time complexity for a community-based algorithm is $O(m^{\prime }n)\simeq O(n)$ .

Traditional memory-based collaborative filtering algorithms directly calculate similarities between target users and all other $m$ users. The algorithms have no offline time and only have online time. In order to calculate the similarity between the target user and another user, they first need to find common rating items between users. Thus calculating similarities between the target user and all $m$ users requires community $O(mn)$ time complexity. Thus a community-based user domain algorithm has obvious advantages in online time complexity from the above analysis.