User interest-based recommender system for image-sharing social media

Abstract

Nowadays, many people use social media to communicate with others, share their interests and obtain information. As the performance of the embedded cameras on mobile phones improve, image-sharing social media became a popular tool for people to communicate with others and share their interests, which yields vast amount of data related to the users’ interests. However, only few studies pay attention to analyze data in image-sharing social media and utilize it to perform appropriate services, such as recommendation. We propose a framework to discover user interests using the Latent Dirichlet Allocation (LDA) based topic model and to recommend protentional friends and POIs related to the target user’s interests. To do this, we devise the advanced LDA based topic model which can be utilized in image-sharing social media by exploiting both textual features and visual features. In addition, the novel method to discover user interest is proposed by generating topic graph to represent the user interest as graph-shape, which is an effective way to completely describe the user interest as explicit form. Lastly, we propose a method to recommend POIs and potential friends to the target user by calculating graph similarity between topic graphs. To demonstrate the superiority of our framework, we collected real data from image-sharing social media and conducted comparison experiments with state-of-the-art methods.

1 Introduction

In recent, social media has become a dominant tool for people to communicate with each other and maintain relationships. Especially, the spread of smartphones with high-performance cameras has made image-sharing social media popular. Instagram, for example, had 90 million active users in 2013, but now has more than a billion active users, is positioning one of the most popular social media in the world [1]. Naturally, these kinds of social media are utilized by the users to establish and maintain social relationships with other people, as other text-based social media do. However, image-sharing social media are more focused on expressing and sharing users’ interests while text-based social media have been mainly used for conversations between users [2]. At this time, the user interests are defined as subjects or activities that the user pays attention to or likes to do. That is, it is clear that image-sharing social media contain a wealth of high-quality information to understand users’ interests than text-based social media. The information about users’ interests is a key to improve the recommendation and users’ satisfaction in social media. In fact, many social media users search the other users with similar interests and points-of-interests (POIs) which meet their interests [2,3,4]. Although discovering information of user interests is very important to perform appropriate recommendation, only a few researchers have performed to discover the user interests from posts in image-sharing social media and recommend potential friends or POIs to satisfy the users.

The previous studies mainly performed based on text-based social media with additional location information such as POIs or trajectory GPS data [5,6,7,8,9,10,11,12,13,14,15]. Thus, most of them pay attention to process the noise or sparsity of texts using Latent Dirichlet Allocation (LDA) and LDA-based topic models. Since the text data in image-sharing social media is even more sparse than text-based social media, their models cannot be directly applied in image-sharing social media. Some researchers have tried to utilize visual features or metadata of the images instated of text to recommend contents, potential friends, and POIs in image-sharing social media [3, 4, 16,17,18]. However, these methods using vision computing have the following limitations. First, the visual features extracted by CNN or SIFT is insufficient to discover various user interests since some of them can be discovered in a text. Second, methods which has high computational burden are hard to cover the dynamically changing social media topics. Therefore, it is necessary to discover various user interests using both text as well as images by using methods which has low computational burden to cope with the characteristics of social media data such as dynamics and hugeness.

In the previous work, we proposed a method to generate the individuals’ topic graph which represent explicit and implicit interests of each user [19]. This paper extends the previous work by proposing User inteRest-Based User/POI RecommendAtioN (URBAN) framework to recommend potential friends and POIs based on the discovered individual topic graphs. The major improvements and contributions of this paper are presented as follows.

• In the previous work, in order to improve the conventional LDA based topic modeling, we proposed the LDA-IL that exploits the image tags instead of words. However, since image tags only composed of limited terms, the kinds of topics discovered by the model are restricted. To overcome this limitation, we propose an advanced topic model named Mixed Topic Model for Image-sharing Social media (MTMIS), which uses both hashtags and image tags. The hashtags have compressed and structured information than plain texts, and also the image tags are directly related to user interests. Consequently, both hashtags and image tags are important to completely discover uses’ interests.

• In this paper, we propose a novel method to generate two types of topic graphs composed of topics discovered by MTMIS. The first type of topic graph is ‘general topic graph,’ which is a topic graph to describe the entire interests of the users in the social media. On the other hand, the ‘individual topic graph,’ which is created based on the general topic graph, is a topic graph to describe the interests of a specific user or POI. The reason to define two distinct types of topic is to overcome difficulty of the LDA-based topic model in finding personal interests and to alleviate differences between kinds of topics discovered over the users.

• Finally, we propose a recommendation method using the graph similarity among individual topic graphs. To calculate graph similarity, maximum common subgraph (MCS) can be utilized [20]. In fact, the conventional MCS detection methods require high computational resources to process the graphs. However, since the topic graphs generated from social media should be dynamically up-to-dated, we propose the simple and light MCS detection method using defined two types of topic graphs.

This paper is organized as follows. In Sect. 2, we describe related works about topic models for discovery of user interests, and user/POI recommendations in social media. The structure and properties of the proposed MTMIS model are described in Sect. 3. Sect. 4 describes the overall architecture and procedure of the URBAN framework. In Sect. 5, we demonstrate our prototype system and show the performance through several experiments. Finally, Sect. 6 puts forth the conclusions and suggests further research in connection with the proposed framework.

2 Literature review

2.1 Topic models for discovery of user interests from social media

Nowadays, social media became popular platform for people to communicate with each other and share interests. Since it contains lots of data related to its users, many studies have been performed to discover user interests from social media [21]. Since texts in social media are sparse and noisy, LDA model cannot be directly applied to discover topics of the user interests. However, LDA is a still powerful method to find topics in documents, so many studies have proposed their own topic models based on conventional LDA model. The modified LDA-based model to discovery user interest are summarized in Table 1.

Table 1 Topic models to discover user interests from social media

Twitter-User model is proposed by modifying the Author-Topic Model (ATM) [22] to discover user interests from Twitter [5]. Hashtag Graph-based Topic Model (HGTM) utilizes hashtags’ co-occurrence of the tweets since hashtags make tweets semi-structured and semantically related to each other [6]. User-Topic model divided the user interests by two kinds, which are original interests and retweet interests [7]. Based on this assumption, User-Topic model separately utilizes original texts and retweet texts in the topic discovery process. Guided LDA is devised to discover interest relationship between each pair of users [8]. To do so, user behaviors, such as reposting, commenting, and replying, are considered in their model. Aggregated LDA utilizes the textual information associated with POIs to infer the users’ interests of POIs from the location-based social networks (LSBNs) [9]. Spatial-Temporal LDA (ST-LDA) model is also developed to discover interests from the LSBNs [10]. Based on the assumption that users tend to have different interests when they travel in different regions, ST-LDA model uses the content information of checked-in POIs to infer the users’ interests on POIs.

The studies to discover user interests from the social media are conducted based on text-based social media such as Twitter, Sina, and location based social media such as Foursquare and Yelp. However, they cannot be applied to image-sharing social media, since the proposed models are developed suitable to the only textual or numerical data, not images. Also, image-sharing social media represent high sparsity and noise for textual data, the novel model is needed to discover the users’ interests from the media.

2.2 User interest-based recommender systems in social media

Many studies have been performed to recommend posts, tags, potential friends, and POIs based on the interests of the target user to improve user satisfaction, as summarized in Table 2.

Table 2 User interest-based recommender systems in social media

In case of text-based social media, most studies are performed to recommend potential friends to the target user [11, 13, 14]. To do so, latent topics are discovered by using topic models, and Kullback Leibler (KL) divergence is utilized to calculate similarity between the topic distributions of the users. Hashtag-LDA was proposed to recommend the most relevant hashtags to the target user, which enhances the influence of hashtags on latent topics’ generation [12]. Most of the recommender systems which are developed on a basis of LSBNs aimed to recommend POIs that meet the interests of each user [9, 10, 15]. Considering the characteristics of the social media platform where the research is performed, some researchers have developed their own topic models to discover user interests [9, 10]. Based on the discovered topics, Topic and Location-aware Probabilistic Matrix Factorization (TL-PMF) method is proposed to perform POI recommendation by considering both the extent to which the target user’s interests match the POI and the word-of-mouth opinions of the POI [9]. The heuristic-based method is designed to exploit an effective attribute pruning (AP) algorithm that can support to fast online recommendation on the large-scale dataset [10]. Also, other research proposed a generic graph-based embedding model (GE) and a time-decay method to handle data sparsity and cold start issue, and to dynamically track the target user’s latest preferences [15].

In case of image-sharing social media, some recommender systems were developed for Flicker and aim to perform personalized POI recommendations based on the target user’s images [3, 16]. The author-topic based collaborative filtering (ATCF) method is proposed to enable POI recommendation when the target user visits a new place by discovering topics from the images’ metadata [16]. Besides, Visual-enhanced Probabilistic Matrix Factorization model (VPMF) was proposed, which adds visual features of the images into the collaborative filtering model [3]. Some recommender systems have been developed based on Instagram [4, 17, 18]. One of them utilizes external knowledge base to build relationships between hashtags and perform picture recommendation based on the correlations [17]. Another method is developed to discover topical authorities related to the target user by inferring topical interests from the user’s biography, propagating interests over the follower graph, and assigning topics to authorities [18]. Also, CNN-based methods have been proposed to extract the visual features from the images and perform visual content enhanced POI recommendation [4].

3 Mixed topic model for image-sharing social media

To discover latent topics in the posts of image-sharing social media, we develop a novel topic model named Mixed Topic Model for Image-Sharing social media (MTMIS) by modifying the conventional LDA [23]. The difference from LDA is that MTMIS utilizes both textual and visual data to discover the users’ interests in social media. At this time, hashtags are used as textual data, and image tags, which are obtained by image recognition, are used as visual data. In this section, we introduce MTMIS model by providing generative process and equations for inference.

3.1 Generative process

As mentioned above, MTMIS exploits both hashtags and image tags. Thus, we design the model as it separately utilizes hashtags and image tags considering their characteristics. The graphical representation of MTMIS is depicted in Fig. 1. While the hashtag distribution and image tag distribution on the topics are estimated separately, the topic distribution on the posts is estimated considering both topics of the hashtags and image tags contained in each post. Also, in this model, each image in the same post has the same weight on the topic distribution on the post, regardless of the number of image tags contained in each image. The definitions and notation used in MTMIS are represented in Table 3.

Fig. 1

Graphical representation of MTMIS

Table 3 Definitions and notation for MTMIS model

In this model, only hashtags and image tags are observable, and other variables are hidden. To infer hidden topics from posts, MTMIS assumes the generative process represented as follows:

• 1. For each topic k = 1…1K:

  • a.
    $$ {y}_{dl}\sim Multinomial\left({\theta}_d\right) $$
  • b.
    $$ {h}_{dl}\sim Multinomial\left({\varPhi h}_{y_{dl}}\right) $$

• 2. For each post d = 1…D:

  • a.
    $$ {i}_{dmn}\sim Multinomial\left({\varPhi i}_{z_{dmn}}\right) $$

  • b. For each hashtag l = 1…L_d:

    • i.
      $$ \mathrm{Draw}\kern0.5em {y}_{dl}\sim Multinomial\left({\theta}_d\right) $$
    • ii.
      $$ \mathrm{Draw}\kern0.5em {h}_{dl}\sim Multinomial\left({\varPhi h}_{y_{dm}}\right) $$

  • c. For each image m = 1…M_d:

    • i. For each image tag n = 1…N_dm:

      • 1. Draw z_dmn~Multinomial(θ_d)

      • 2.
        $$ \mathrm{Draw}\kern0.5em {i}_{dmn}\sim Multinomial\left(\Phi {i}_{z_{dmn}}\right) $$

3.2 Parameter estimation

Using the generative process depicted above, inference process is performed to estimate hidden variables based on h_1 : D and i_{1 : D, 1 : M} which are observable. The notation used in MTMIS are represented in Table 4.

Table 4 Definitions and notation for inference process

In MTMIS, the total joint probability of the model is:

$$ p\left({y}_{dl}=k\ |\ {h}_{dl}={wh}_h,{\boldsymbol{y}}_{1:D,- dl},{\boldsymbol{z}}_{d{M}_d},{\boldsymbol{h}}_{1:D}\right)\propto \left({\gamma}_h\frac{Nh_{dk,- dl}^{DK}+\alpha }{\sum \limits_{k^{\prime }=1}^K{Nh}_{d{k}^{\prime },- dl}^{DK}+ K\alpha}+\frac{\gamma_i}{M_d}\sum \limits_{m^{\prime }=1}^{M_d}\frac{Ni_{d{m}^{\prime }k}^{DK}+\alpha }{\sum \limits_{k^{\prime }=1}^K{Ni}_{d{m}^{\prime }{k}^{\prime}}^{DK}+ K\alpha}\right)\bullet \frac{Nh_{kh,- dl}^{KH}+\beta }{\sum \limits_{h^{\prime }=1}^H{Nh}_{k{h}^{\prime },- dl}^{KH}+ H\beta} $$

To infer Φh, Φi, and θ which minimize the conditional probability p(y_1 : D, z_1 : D, Φh, Φi, θ | h_1 : D, i_{1 : D, 1 : M}), we can apply Gibbs sampling method. By marginalizing the above equation, conditional probability of assigning topic k to l^th hashtag and assigning topic k to n^th image tag of m^th image in post d can be derived as follows.

$p\left({y}_{dl}=k\ |\ {h}_{dl}={wh}_h,{\boldsymbol{y}}_{1:D,- dl},{\boldsymbol{z}}_{d{M}_d},{\boldsymbol{h}}_{1:D}\right)\propto \left({\gamma}_h\frac{Nh_{dk,- dl}^{DK}+\alpha }{\sum_{k^{\prime }=1}^K{Nh}_{d{k}^{\prime },- dl}^{DK}+ K\alpha}+\frac{\gamma_i}{M_d}\sum \limits_{m^{\prime }=1}^{M_d}\frac{Ni_{d{m}^{\prime }k}^{DK}+\alpha }{\sum_{k^{\prime }=1}^K{Ni}_{d{m}^{\prime }{k}^{\prime}}^{DK}+ K\alpha}\right)\bullet \frac{Nh_{kh,- dl}^{KH}+\beta }{\sum_{h^{\prime }=1}^H{Nh}_{k{h}^{\prime },- dl}^{KH}+ H\beta}$

$$ {\displaystyle \begin{array}{l}p\left({z}_{dmn}=k\ |\ {i}_{dmn}={wi}_i,{\boldsymbol{z}}_{1:D,1M,- dmn},{\boldsymbol{y}}_d,{\boldsymbol{i}}_{1:D,1:M}\right)\\ {}\propto \Big\{{\gamma}_h\frac{Nh_{dk}^{DK}+\alpha }{\sum_{k^{\prime }=1}^K{Nh}_{d{k}^{\prime}}^{DK}+ K\alpha}\\ {}+\frac{\gamma_i}{M_d}\left(\frac{Ni_{dmk}^{DK}+\alpha }{\sum_{k^{\prime }=1}^K{Ni}_{d{mk}^{\prime },- dmn}^{DK}+ K\alpha}+\sum \limits_{\begin{array}{c}{m}^{\prime }=1\\ {}{m}^{\prime}\ne m\end{array}}^{M_d}\frac{Ni_{d{m}^{\prime }k}^{DK}+\alpha }{\sum_{k^{\prime }=1}^K{Ni}_{d{m}^{\prime }{k}^{\prime}}^{DK}+ K\alpha}\right)\Big\}\\ {}\bullet \frac{Ni_{ki,- dmn}^{KI}+\beta }{\sum \limits_{i^{\prime }=1}^I{Ni}_{k{i}^{\prime },- dmn}^{KI}+ I\beta}\end{array}} $$

In these equations, topic allocation of l^th hashtag in post d is affected by not only topics of hashtags, but also by topics of image tags in post d, and vice versa. Based on the equations above, Gibbs sampling can be performed. Results of Gibbs sampling are the distribution of hashtags and image tags on the topics (Φh and Φi) and the distribution of topics on the posts (θ) as represented as follows:

${\displaystyle \begin{array}{c}{\varPhi h}_{kh}\propto \frac{Nh_{kh}^{KH}+\beta }{\sum_{h^{\prime }=1}^H{Nh}_{kh\prime}^{KH}+ H\beta}\\ {}\begin{array}{c}{\varPhi i}_{ki}\propto \frac{Ni_{ki}^{KI}+\beta }{\sum_{i^{\prime }=1}^I{Ni}_{k{i}^{\prime}}^{KI}+ I\beta}\\ {}{\theta}_{dk}\propto {\gamma}_h\frac{Nh_{dk}^{DK}+\alpha }{\sum_{k^{\prime }=1}^K{Nh}_{d{k}^{\prime}}^{DK}+ K\alpha}+\frac{\gamma_i}{M_d}\sum \limits_{m^{\prime }=1}^{M_d}\frac{Ni_{d{m}^{\prime }k}^{DK}+\alpha }{\sum_{k^{\prime }=1}^K{Ni}_{d{m}^{\prime }{k}^{\prime}}^{DK}+ K\alpha}\end{array}\end{array}}$

4 Procedural architecture of URBAN framework

Based on the discovered topics for each post using MTMIS, the interests of the users are discovered, and recommendation of potential friends and POIs can be performed based on the target user’s interests. In this section, we will explain the detailed process of the framework we have developed to perform user interest-based recommendation. At first, we provide a simple scenario to illustrate the necessity for discovery of user interests using topic graph and user/POI recommendation based on the topic graph and the overall of URBAN framework and the detailed process will be explained.

4.1 Illustrative scenario

Jane is a 22-years-old woman who studies in Manila. She likes to play tennis with her tennis club members at the riverside. Also, she usually takes pictures of playing tennis with the scenery of the riverside and uploads the pictures in Instagram. In the next semester, Jane will study at a university located in Seoul by the exchange program. Jane wants to know the places in Seoul where she may be interested in, and the people who she can share her interests. However, there are so many places and people in Seoul so that Jane cannot easily distinguish the appropriate ones on her own.

Based on our framework, Jane’s topic of interests can be modelled as an individual topic graph as depicted in the left pane of Fig. 2. In this graph, both Jane’s explicit interests and implicit interests are modeled as vertices of the graph, and their relations are modeled as edges. The explicit interest means an interest that can be found directly from posts uploaded by a user, and the implicit interest is defined as an interest to be expected of the user based on general interests of others. Using this graph, POIs and potential friends which share similar interests with Jane can be recommended based on graph similarity.

Fig. 2

Illustrative scenario of URBAN framework

4.2 Procedural architecture of URBAN framework

We have developed User inteRest-Based user/POI recommendAtioN (URBAN) framework which can discover user interests from user created posts and perform recommendation based on the interests. URBAN framework consists of three modules, which are general topic graph generation module, individual topic graph extraction module, and graph similarity-based recommendation module. The overall framework is depicted in Fig. 3.

Fig. 3

Procedural architecture of URBAN framework

4.3 Detailed descriptions of the modules

4.3.1 General topic graph generation module

This module discovers topics from the random sampled dataset and generates general topic graph by modelling relations between the topics. General topic graph represents interests of all kinds of Instagram users, and further is utilized in the individual topic graph extraction process. The reason why we first generate topic graph from the random sampled dataset is to obtain unbiased topics. Also, it enables the comparison between individual graphs, since individual topic graphs are extracted from the same general topic graph.

• Generate random sampled dataset using Instagram API with computer vision tool

In case of Instagram, one or more image is mandatory and the others (hashtags, text, and POI) are optional in the posts. While text is extremely sparse and noisy, hashtags are more refined and commonly shared. Also, images in the posts contain meaningful information of the user interests. Based on this information, we utilize hashtags and images of the posts to discover topics and generate topic graph. To analyze image data, we utilize computer vision tool, such as MS Azure Computer Vision API, to collect image tags from the images in each post. We define the post as follows:

Definition 1

d^th Post (p_d) p_d is a set of hashtags and image tags, and is simply represented as

${p}_d=\left[{\boldsymbol{h}}_d,{\left\{{\boldsymbol{i}}_{dm}\right\}}_{m=1}^{M_d}\right]$where h_d is a set of hashtags, M_d is a number of images in p_d, and i_d is a set of image tags in m^th image of post d as mentioned in the previous section. The random sampled dataset (p) can be represented as follow.

$$ \boldsymbol{p}=\bigcup \limits_{d=1}^D{p}_d $$

where D is the total number of posts in the dataset.

• Discover topic distribution on each post using MTMIS based inference process

Based on the random sampled dataset we have collected, MTMIS based inference process is performed to discover latent topics. Gibbs sampling algorithm for inference process is presented in Fig. 4 by referring to [6]. To infer topic-hashtag distribution (Φh), topic-image tag distribution (Φi), and post-topic distribution (θ) from the dataset p, topics of each hashtag and each image tag are iteratively allocated and counted.

Fig. 4

Gibbs sampling algorithm for discovery of general topics

• Calculate co-occurrence between topics using cosine similarity

To calculate co-occurrence between topics in posts, post-topic distribution (θ) is utilized. In this matrix, each row represents topic distribution for each post. On the other hand, each column represents the occurrence of the posts to each topic. Using these columns, we define post distribution as suggested as follow.

Definition 2

Post distribution of k^th Topic (TP_k) TD_k is a D-dimension vector which contains the topic k’s probability on each post. It is a k^th column of θ and can be represented as.

$$ {TP}_k=\left\{\ \frac{\theta_{1k}}{csum_k},\frac{\theta_{1k}}{csum_k},\dots, \frac{\theta_{dk}}{csum_k},\dots, \frac{\theta_{Dk}}{csum_{k.}}\right\} $$

where θ_dk is the probability of the topic k on the d^th post, and ${csum}_k=\sum \limits_{d=1}^D{\theta}_{dk}$. Based on these post distributions, co-occurrence between each pair of topics is calculated using cosine similarity as depicted as follow.

$$ {co}_{k{k}^{\prime }}=\frac{TP_k\bullet {TP}_{k^{\prime }}}{\left\Vert {TP}_k\right\Vert \left\Vert {TP}_{k^{\prime }}\right\Vert } $$

and topic co-occurrence set (co) contains co-occurrences of every pair of topics.

$$ \boldsymbol{co}=\left\{{co}_{k{k}^{\prime }}|k=1\dots K,{k}^{\prime }=1\dots K,k\ne {k}^{\prime}\right\} $$

• Generate general topic graph based on discovered topics and their relations

Based on discovered topics and their co-occurrence, general topic graph is generated. In this graph, topics are allocated as vertices, and relations between these topics are allocated as edges. The general topic graph can be defined as follow.

Definition 3

The General Topic Graph (${\mathbf{\mathcal{G}}}_{\boldsymbol{G}}$) ${\mathcal{G}}_G$ is the undirected connected graph which can be represented by

$$ {\mathcal{G}}_G=\left({V}_G,{E}_G\right) $$

where V_G is the set of vertices which represents the discovered topics, and E_G is the set of edges which represents topic relations.

Generation of general topic graph should meet the two conflicting requirements: 1) topic relation should include the pairs of topics which have high co-occurrence value, and 2) the general topic graph should be the connected graph. A connected graph is a graph in which it is possible to get from every vertex in the graph to every other vertex through a series of edges. The reason why the general topic graph should be connected is to enable personalized topic graph extraction which uses shortest path algorithm. To fulfill this requirement, it is advantageous for ${\mathcal{G}}_G$ to contain as many edges as possible. However, considering the values of co-occurrences between topics, only some of them has meaningful value and others have very low value, like the Pareto distribution. Considering the two conflicting requirements, we have developed a heuristic method to generate general topic graph. First, all topic co-occurrences which has higher value than the average are allocated as topic relation. Second, for every topic k which does not have any relation with the other topics, allocate the maximum topic co-occurrence which one of the pair of topics is k as a topic relation. The detailed process is depicted in Fig. 5.

Fig. 5

General topic graph generation algorithm

4.3.2 Individual topic graph extraction module

This module is performed to discover and relate the topics of interests for each user/POI’s posts. To do so, each user/POI’s posts are separately collected, and topics are allocated on these posts. Based on the allocated topics, individual topic graph is extracted from the general topic graph using the topic weights.

• Discover topic distribution of each user/POI’s posts

To model each user/POI’s topics of interests, each user/POI’s posts are collected. Individual posts can be defined as follow. The d^th Post of u^th user/POI (up_ud) can be represented as

$$ {up}_{ud}=\left[{\boldsymbol{uh}}_{ud},{\left\{{\boldsymbol{ui}}_{ud m}\right\}}_{m=1}^{uM_{ud}}\right] $$

where uh_ud is a set of hashtags and ui_udm is a set of image tags in the m^th image of up_ud. The dataset of the u^th user/POI (up_u) can be represented as follow.

${\boldsymbol{u}\boldsymbol{p}}_{\boldsymbol{u}}=\bigcup \limits_{d=1}^{D_u}{up}_{ud}$where D_u is the total number of posts in the dataset.

For each user/POI’s dataset, MTMIS based inference process is performed. Unlike the inference process depicted above, which is performed to infer Φh, Φi, and θ, we utilize Φh and Φi to allocate topics to each user/POI’s posts. That is, topic-hashtag distributions (Φh) and topic-image tag distributions (Φi) we have discovered in the former module are used to allocate topics to the hashtags (uh_ud) and image tags (ui_ud) of the u^th user/POI’s posts (up_u). By doing so, we can discover the topics of the user/POI’s posts (uθ_u). The notation for individual topic inference process is represented in Table 5, and detailed inference process is depicted in Fig. 6.

Table 5 Definitions and notation for individual topic inference process

Fig. 6

Gibbs sampling algorithm to allocate topics for each user/POI’s posts

• Calculate weights of the topics and their co-occurrence

Performing inference with Φh, Φi and up_u, we can acquire the uθ_u which is the topic distribution for each user/POI’s post. uθ_u is a D_u × K matrix and uθ_udk is an element of d^th row and k^th column, which represents topic k’s probability for d^th post. While the row of this matrix uθ_ud = {uθ_ud1, uθ_ud2, …, uθ_udk, …, uθ_udk} represents topic distribution allocated over posts, the column of the matrix is a vector which contains probability of specific topic to each posts. Using the column of uθ_u, the weight of each topic for the specific user/POI can be calculated. The topic weight is defined as follow.

Definition 4

The Topic Weight (TW_uk) TW_uk is the weight of topic k in the u^th user/POI’s posts. It can be calculated by dividing the total number of the user/POI’s posts from the total sum of k^th column of uθ_u, as represented as follow.

$$ {TW}_{u k}=\frac{\sum_{d=1}^{D_u}{u\theta}_{u dk}}{D_u} $$

Using this topic weight, the topics of interests of the u^th user/POI can be discovered by comparing the topic weight of each topics with the average topic weight. Since these topics are discovered directly from the individual user/POI’s posts we define them as the individual topics of explicit interests as suggested as follow.

Definition 5

The Individual Topics of Explicit Interests (UTE_u) UTE_u is the set of topics that are explicitly related to the u^th user/POI.

$$ {UTE}_u=\left\{k\ |\ {TW}_{uk}>\frac{\sum_{k^{\prime }=1}^K{TW}_{u{k}^{\prime }}}{K},k=1,2,\dots, K\right\} $$

After the u^th user/POI’s topics of explicit interests are discovered, co-occurrence is calculated for every pair of topics in UTE_u to generate individual topic graph. To discover relation between topics, we calculate cosine similarity between topics and discriminate pairs of topics which has higher similarity value then the average, as suggested in the previous module. We define the individual topic relation as follow.

Definition 6

The Individual Topic Relations (UTR_u) UTR_u is the set of pairs of topics which has co-occurrence value higher than the average value, and it can be represented as follow.

$$ {UTR}_u=\left\{\left(k,{k}^{\prime}\right)\ |\ {co}_{k{k}^{\prime }}>\frac{2{\sum}_{a=1}^{K-1}{\sum}_{b=a+1}^K{co}_{ab}}{K\left(K-1\right)},k\in {UTE}_u,{k}^{\prime}\in {UTE}_u,k\ne {k}^{\prime}\right\} $$

• Extract individual topic graphs from the general topic graph

Using UTE_u and UTR_u, individual topic graph can be generated by extracting the general topic graph. Individual topic graph can be defined as follow.

Definition 7

The Individual Topic Graph (${\boldsymbol{u}\mathbf{\mathcal{G}}}_{\boldsymbol{u}}$) ${u\mathcal{G}}_u$ is the undirected connected graph to represent topics of interests of each user/POI, which can be represented by

$$ {u\mathcal{G}}_u=\left({uV}_u,{uE}_u\right) $$

where uV_u is the set of vertices which represents the user/POI’s topics of explicit/implicit interests, and uE_u is the set of edges which represents the user/POI’s topic relations.

The generation process of individual topic graph is performed as follow. First, the individual topics of explicit interests UTE_u are allocated as vertices uV_u of the individual topic graph ${u\mathcal{G}}_u$. Since topics in UTE_u are discovered based on the topics of the general topic graph ${\mathcal{G}}_G$, uV_u is the subset of vertices V_G of the general topic graph (uV_u ⊂ V_G). However, it is possible for the individual topic relations (UTR_u) to have relations which are not contained in E_G. For every pair of topics (k, k^′) in UTR_u which are contained in E_G, $\left({V}_k,{V}_{k^{\prime }}\right)$ is directly allocated as an element of the edges uE_u of ${u\mathcal{G}}_u$. On the other hand, for every pair of topics (k, k^′) in UTR_u which are not included in E, shortest path with two end vertices V_k and ${V}_{k^{\prime }}$ is extracted from ${\mathcal{G}}_G$. Shortest path can be defined as follow.

Definition 8

The Shortest Path (${\mathbf{\mathcal{G}}\boldsymbol{s}}_{\boldsymbol{k}{\boldsymbol{k}}^{\prime }}$) ${\mathcal{G}s}_{k{k}^{\prime }}$ is the subgraph of ${\mathcal{G}}_G$ that is a path graph of which two end vertices are V_k and ${V}_{k^{\prime }}$.

$$ {\mathcal{G}s}_{k{k}^{\prime }}=\left({Vs}_{k{k}^{\prime }},{Es}_{k{k}^{\prime }}\right) $$

where ${Vs}_{k{k}^{\prime }}$ and ${Es}_{k{k}^{\prime }}$ are vertices and edges of the shortest path. End vertices are the vertices which are connected to only one edge. The shortest path is extracted based on Dijkstra’s algorithm [24].

The vertices included in ${Vs}_{k{k}^{\prime }}$ and edges included in ${Es}_{k{k}^{\prime }}$ are added to uV_u and uE_u. By doing so, an individual topic graph is generated as a subgraph of the general topic graph. This individual topic graph generation method has two advantages. First, since all individual topic graphs are subgraphs of the general topic graph, comparison between individual topic graphs can be easily performed. Second, by extracting shortest path from the general topic graph, the individual topics of implicit interests can be discovered. Individual topic of implicit interests is the topic that is not directly represented in the target user/POI’s posts, but it is highly related to the topics which are represented in the target user/POI’s posts according to the general topic graph. The topics extracted from the shortest path except the two end vertices can be the individual topics of implicit interests. The detailed generation process of individual topic graph is suggested in Fig. 7.

Fig. 7

Individual topic graph generation algorithm

4.3.3 Graph similarity-based recommendation module

This module is performed to recommend potential friends and POIs which have the similar individual topic graphs to the target user. To perform the recommendation, we first calculate the graph similarity between the target user and the other users and POIs. Based on the graph similarity, each user/POI is scored in the perspective of the target user and recommendation is performed.

• Discover maximum common subgraphs between individual topic graphs

To calculate similarity of the graphs, maximum common subgraphs (MCS) of the pairs of the individual topic graphs are detected. Because MCS problem has exponential-time complexity [25], it requires high computational resources. However, since all individual topic graphs are structured based on the same general topic graph, they are composed of same kinds of vertices and edges, so that maximum common vertices and edges can easily be discovered. Maximum common subgraph in our work can be defined as follow.

Definition 9

The Maximum Common Subgraph (${\mathcal{G} mcs}_{\boldsymbol{u}{\boldsymbol{u}}^{\prime }}$) ${\mathcal{G} mcs}_{\boldsymbol{u}{\boldsymbol{u}}^{\prime }}$ is the MCS of two individual topic graphs ${u\mathcal{G}}_u$ and ${u\mathcal{G}}_{u^{\prime }}$, which can be represented as follow.

$$ {\mathcal{G} mcs}_{\boldsymbol{u}{\boldsymbol{u}}^{\prime }}=\left({Vmcs}_{u{u}^{\prime }},{Emcs}_{u{u}^{\prime }}\right) $$

where ${Vmcs}_{u{u}^{\prime }}={uV}_u\cap {uV}_{u^{\prime }}$ and ${Emcs}_{u{u}^{\prime }}={uE}_u\cap {uE}_{u^{\prime }}$.

• Calculate the score of potential friends/POIs using graph similarity

Based on the MCSs detected between individual topic graphs, scoring each user/POI based on the target user’s topics of interests can be performed. We propose a novel scoring method for evaluating the potential friends/POIs using the MCU, which is defined as follow.

Definition 10

The User Interest-based Score (UIS_u) UIS_u is the function for scoring the potential friends/POIs’ individual topic graphs (${u\mathcal{G}}_{u^{\prime }}$) in the perspective of the target user’s graph (${u\mathcal{G}}_u\Big)$.

$$ {UIS}_{\boldsymbol{u}}\left({u}^{\prime}\right)={Nscore}_u\left({u}^{\prime}\right)\bullet {Escore}_u\left({u}^{\prime}\right) $$

where ${Nscore}_u\left({u}^{\prime}\right)=\frac{n\left({Vmcs}_{u{u}^{\prime }}\right)}{n\left({uV}_u\right)}$ and ${Emcs}_{u{u}^{\prime }}=\frac{n\left({Emcs}_{u{u}^{\prime }}\right)}{n\left({uE}_u\right)}$. Using this method, potential friends and POIs which share similar interests can be recommended to the target user.

5 Experiments

In this section, we have performed two kinds of experiments to show the effectiveness of our research. To do so, we collected posts from Instagram, and transformed images to image tags using MS Azure Computer Vision API. In the first experiment, we compared the perplexity and accuracy of MTMIS model with the baselines to show the superiority of MTMIS in discovering topics from image sharing social media. Second, we calculated precision and recall of the recommendation to show the effectiveness of URBAN framework.

5.1 Experimental settings

The experiments are performed based on the dataset of hashtags and image tags collected from Instagram. The dataset is composed of 1600 posts, which contains more than 3000 images. The users and POIs in the dataset are related to U.S. state of North Carolina. We let the Dirichlet hyperparameters as α = 50/K, βh = 0.1, and βi = 0.1. To balance the volume of the hashtags and image tags, we allocated the weight of hashtags γ_h as 0.2, and the weight of images γ_i as 0.8.

5.2 Comparison of the topic models

To demonstrate the superiority of the MTMIS model, we have performed Gibbs sampling and evaluate the performance in terms of perplexity. In this experiment, three kinds of methods are utilized as baselines: LDA with only image tags (LDA-I) and LDA with both hashtags and image tags (LDA-HI). Since hashtags are much sparser than image tags in image-based social media, it is inappropriate to compare the topic model using hashtags. The example of the hashtags and image tags contained in the topics are depicted in the Table 6.

Table 6 An example of discovered topics of MTMIS model

First, to evaluate the predictive performance in terms of perplexity, we calculate perplexity score of MTMIS and LDA by changing the iteration times and number of topics. In this experiment, since LDA-I uses only image tags on the dataset, comparison of perplexity with the other two model (MTMIS and LDA-HI) could be biased. Therefore, we compared MTMIS and LDA-HI by changing the iteration times and the number of topics except LDA-I. The result is depicted in Fig. 8.

Fig. 8

Perplexity comparison by varying iteration times (left) and number of topics (left)

Since the dataset is composed of refined terms, which are hashtags and image tags, the perplexity is considerably low relative to the result of natural language posts from text-centric social media. In both cases, perplexity LDA-HI rapidly decreases as iteration times or number of topics increase and converges to local optimum. On the other hand, the perplexity graphs of MTMIS are gentle curved and outperformed LDA-IL for every case. It represents that predictive performance of MTMIS is better than LDA over time in predictive performance and its stability.

Second, to evaluate the topic discovery performance of the MTMIS and baselines with the topics of the users, we have calculated topic discovery accuracy (AC) based on the following equation [26].

$$ AC=\frac{\sum_{d=1}^D\delta \left({e}_d,{g}_d\right)}{D} $$

where D is the total number of posts in the dataset, δ(x, y) is the delta function which has a value 1 if x = y and 0 otherwise, e_d represents the estimated topic of the post d using the topic models, and g_d represents the ground truth. We have calculated the accuracy of the results of the three models by increasing the number of topics, as depicted in Fig. 9.

Fig. 9

Accuracy of MTMIS and LD

In all cases, MTMIS outperformed the baseline models, and the accuracy of LDA-I was better than LDA-HI. It is because LDA-HI does not consider the distinctive traits of hashtags and image tags, and it regards the terms of both hashtags and image tags have the same weight. Since the image tags are consist of limited terms automatically generated from computer vision tool while the hashtags are created directly by users and contain variety of colloquialisms, they should be separately handled. This experiment has proved that MTMIS model performs better than ordinary LDA model in case of image sharing social media. Also, the MTMIS can properly handle mixed posts with text and images to discovery topics.

5.3 Evaluation of recommendation

In URBAN framework, recommendation on potential friends/POIs is performed using individual topic graph. An example of the individual topic graphs by varying the number of topics is depicted in Fig. 10. The example above shows the individual topic graphs of the specific user. As the number of topic increases, each topic became more specific and narrow-scoped.

Fig. 10

Examples of and individual topic graphs

To prove the effectiveness of URBAN framework, we have performed recommendation based on the proposed method. We apply the method in the dataset and evaluate how the method properly recommends the potential friends and POIs which share similar interests to the target user. To evaluate the recommendation, we adopted the precision (PR), recall (RE) and F₁ score as represented as follow:

$$ {\displaystyle \begin{array}{c} PR=\frac{\sum_{u=1}^U\left[\sum \limits_{\begin{array}{c}{u}^{\prime }=1\\ {}{u}^{\prime}\ne u\end{array}}^U\left\{{pru}_u\left({u}^{\prime}\right)\bullet {anu}_u\left({u}^{\prime}\right)\right\}+{\sum}_{p=1}^P\left\{{prp}_u(p)\bullet {anu}_u(p)\right\}\right]}{\sum_{u=1}^U\left[\sum \limits_{\begin{array}{c}{u}^{\prime }=1\\ {}{u}^{\prime}\ne u\end{array}}^U{pru}_u\left({u}^{\prime}\right)+{\sum}_{p=1}^P{prp}_u(p)\right]}\\ {}\begin{array}{c} RE=\frac{\sum_{u=1}^U\left[\sum \limits_{\begin{array}{c}{u}^{\prime }=1\\ {}{u}^{\prime}\ne u\end{array}}^U\left\{{pru}_u\left({u}^{\prime}\right)\bullet {anu}_u\left({u}^{\prime}\right)\right\}+{\sum}_{p=1}^P\left\{{prp}_u(p)\bullet {anu}_u(p)\right\}\right]}{\sum_{u=1}^U\left[\sum \limits_{\begin{array}{c}{u}^{\prime }=1\\ {}{u}^{\prime}\ne u\end{array}}^U{anu}_u\left({u}^{\prime}\right)+{\sum}_{p=1}^P{anp}_u(p)\right]}\\ {}{F}_1=\frac{2\ast PR\ast RE}{PR+ RE}\end{array}\end{array}} $$

where pru_u(u^′) has value 1 if the user u^′ is recommended to the user u by our method, and pru_u(u^′) = 0 otherwise. Also, anu_u(u^′) has value 1 if u^′ is appropriate potential friends to u, and otherwise the value is 0. Likewise, prp_u(p) = 1 if the POI p is recommended to u by the method, and anp_u(p) = 1 if p is a POI which share similar interests with the user u. Based on these measures, we have performed experiments by changing the number of topics, and the result is depicted in Fig. 11.

Fig. 11

Precision, recall and F₁ score of recommendation

The performance of recommendation was best when number of topics is 60 and became worse when the number of topics increases. The reason is that if the number of topics is too large for the dataset, incorrect and unnecessary topics are generated. Since our framework exploits co-occurrence between topics as a topic relation, these unnecessary topics hinders the performance of recommendation. Nevertheless, recommendation based on URBAN framework showed fine performance of recommendation, especially when the number of topics is suitably selected.

6 Conclusion and future works

In this paper, we proposed a novel recommendation method in image-sharing social media, named URBAN framework. First, we devised an advanced topic model called MTMIS for image-sharing social media. It utilizes both two types of data, which are hashtags as textual feature and image tags as visual features, to overcome sparsity and noise of the data. Second, we proposed a method to generate the general topic graph and the individual topic graph. Using this method, unbiased topics of interests can be modelled, and topics of both explicit interests and implicit interests can be discovered for each user/POI. Finally, URBAN framework conducts recommendation of potential friends/POIs based on graph similarity of individual topic graphs. By doing so, not only topics itself but also co-occurrence of topics in each user’s posts is considered in the recommendation process.

We have proved excellence of our method through experimentation, but there are still some limitations. First, we found topics across social media and generated the general topic graph. Since social media data is huge and multivariate, this method is difficult to find informative topic graphs and is also inefficient to deal with huge data. There are similar limitations when doing topic graph pattern matching. By limiting the type of topic graphs as a subgraph of the general topic graph, we have dramatically reduced the computation burden that occurs in graph pattern matching. However, it degrades the discriminativeness of individual topic graphs in recommendation using them.

To overcome these limitations, in the future work, we will adopt the data mining techniques that fully handle the hugeness and dynamics of social media data. To address the hugeness of social media data, we will introduce a feature selection technique that selects only the most important (or informative) features in numerous variables of social media. In addition, to deal with the dynamics, we will consider ensemble learning techniques that can represent the accuracy rate for complex and unknown data shape.