Application graph builder

Disclosed is a system for recommending content of a predefined category to an account holder, or account holders based on the account holder application graphs. The system receives information corresponding to applications executing on the client device of the account holders and generates an application graph for each account holder that includes a list of predefined application categories that are preferred by the account holder. For each predefined category, a list of account holders preferring content relevant to that category is predicted based on the set of generated application graphs.

BACKGROUND

Field of Art

The disclosure generally relates to the field of recommending applications to account holders or determining spam applications, based on an application graph built for the account holder.

Description of Art

There are plenty of mobile applications available and most of the applications include targeted advertisements (ad) for an account holder of the application. The advertisements or the application in general may not always generate useful or good content. Some applications may generate advertisements or messages that may be abusive, in general, may generate bad content. Some applications may be designed to create a fraud, e.g., a click fraud wherein an application clicks on a targeted ad every few minutes. While this activity may make generate revenue every time the ad is clicked on, the longer term impact can be negative as advertisers become frustrated about paying for such ads that have not actually been viewed or for which no meaningful interaction has occurred.

In addition to advertisement fraud, there may be automated account holders or regular account holders in a messaging system that generate irrelevant or fraudulent content, or content of an abusive nature, in the messaging stream of other legitimate account holders. These account holders are generally termed as spam account holders and it is desirable to detect and report these account holders.

Besides fraud, the targeted ads or content sent from a spam account holder may be irrelevant to an account holder of the application and the desired impact of the account holder downloading and executing the targeted ad or following the messages from the spam account holder are low.

Accordingly, determining a spam application or a spam account holder on a client device and generating recommendations that are relevant to an account holder of a client device are highly desired.

DETAILED DESCRIPTION

The Figures (FIGS.) and the following description relate to embodiments by way of illustration only. It should be noted that from the following discussion, alternative embodiments of the structures and methods disclosed herein will be readily recognized as viable alternatives that may be employed without departing from the principles of what is claimed.

Configuration Overview

FIG. 1illustrates an example computing environment100. As shown, the computing environment100includes client devices110(0)-110(N) (collectively, client devices110, and, individually, client device110), a network120, a front end server140, a number of messaging server instances130, a messaging database160, an application graph builder190and an application graph database185. It is noted that the front end server140may comprise one or more server computing machines.

Account holders (in general account holders) use client devices110to access a messaging system in order to publish messages and view and curate their streams. A client device110is a computer including a processor, a memory, a display, an input device, and a wired and/or wireless network device for communicating with the front end server140of the messaging system over network120. For example, a client device110may be a desktop computer, a laptop computer, a tablet computer, a smart phone, or any other device including computing functionality and data communication capabilities.

Each client device110includes an operating system, such as operating system116. The operating system116is a software component that manages the hardware and software resources of the client device110. The operating system116also provides common services to other software applications executing on the client device110. These services may include power management, network management, inter-application communication, etc.

The client devices110also include software applications, such as application T111, application U112, and application V113, comprised of instructions that execute on the processor included in the respective client device110. Each application executing on the client device110is associated with a unique application identifier and performs various functions. Examples of such applications may be a web browser, a social networking application, a messaging application, a gaming application, and a media consumption application. While each of the client devices110may include similar applications, reference will be made only to application T111and application U112executing on client device110(0) for the remaining discussion.

The processor of the client device110operates computer software112configured to access the front end server140of the messaging system so that the account holder can publish messages and view and curate their streams. The software112may be a web browser, such as GOOGLE CHROME, MOZILLA FIREFOX, or MICROSOFT INTERNET EXPLORER. The software112may also be a dedicated piece of software designed to work specifically with the messaging system. Generally, software112may also be a Short Messaging Service (SMS) interface, an instant messaging interface, an email-based interface, an API function-based interface, etc.

The network120may comprise any combination of local area and/or wide area networks. The network can include the Internet and/or one or more intranets, using either wired and/or wireless communication systems.

The messaging system generally provides account holders with the ability to publish their own messages and view messages authored by other accounts. Messages may take a variety of forms including, digital text, videos, photos, web links, status updates, blog entries, tweets, profiles, and the like. The messaging system also may provide various complementary services such as those provided by computing message services and systems such as social networks, blogs, news media, forums, user groups, etc. Additionally, the messaging system could recommend content to an account holder via targeted ads. Examples of messaging systems include FACEBOOK and TWITTER. The messaging system is a distributed network including multiple computing devices, where each computing device in the system includes computer hardware specifically chosen to assist in the carrying out of its specific purpose.

The client device110interface with the messaging system through a number of different but functionally equivalent front end servers140. The front end server140is a computer server dedicated to managing network connections with remote client devices110. As the messaging system may have many millions of accounts, there may be anywhere from hundreds of thousands to millions of connections being established or currently in use between client devices110and the front end server140at any given moment in time. Including multiple front end servers140helps balance this load across multiple countries and continents.

The front end server140may provide a variety of interfaces for interacting with a number of different types of client devices (or client)110. For example, when an account holder uses a web browser112to access the messaging system, a web interface module132in the front end server140can be used to provide the client device110access. Similarly, when an account holder uses an application programming interface (API) type software112to access the messaging system, an API interface module134can be used to provide the client device110access.

The front end server140is further configured to communicate with the other backend computing devices of the messaging system. These backend computing devices carry out the bulk of the computational processing performed by the messaging system as a whole. The backend computing devices carry out any functions requested by a client device110and return the appropriate response (s) to the front end servers140for response to the client device110.

The backend computing devices of the messaging system include a number of different but functionally equivalent messaging servers130. This functionality includes, for example, publishing new messages, providing message streams to be provided upon a request from a client device110, managing accounts, managing connections between accounts, messages, and streams, and receiving engagement data from clients engaging with messages. The application graph builder190and its associated modules, a content recommendation module180and a spam detection module150are described below in reference toFIG. 2.

Application Graph Builder

Using the messaging server130as described withFIG. 1, account holders can form connections with accounts, create streams of messages and engage with those messages. In addition to populating the message streams, the messaging system can provide content to the account holder that the account holder will perceive as useful. To do this, the messaging system uses the application graph builder190to identify a category of applications that the account holder finds interesting and recommend content based on the identified categories of applications.

Referring now toFIG. 2, illustrated are the logical components of an application graph builder and its associated modules, according to one embodiment. The application graph builder190include an application information collection module170, an application graph categorize module175and an associated application graph database185. The spam detection module150accesses the application graph data stored in the application graph database185to detect a spam application or a spam account holder on a client device110. The content recommendation module180accesses the application graph data stored in the application graph database185to recommend content such as applications, advertisements, other account holders to follow, etc. to the account holders of the messaging server130.

The application information collection module170receives information about the applications executing on one or more client devices110. The account holder of the client device110may opt out of information collection from their client device110. The information may include the name of an application, the running time for an application, the usage time of an application, the version of an application and other such information. Based on the collected information, the application information collection module170can infer signals such as the frequently running applications, active applications, dormant applications, keywords for applications that may indicate a category for the application. The process for extracting the application information may be different based on the operating system116of the client device110. For example, the Android operating system allows access by a developer to the running applications information on the client device110. In case of iOS the application information is inferred based on background tasks such as central processing unit (CPU) usage, deep link information or random access memory (RAM) usage of the application.

The application information along with the inferred signals is sent to the application graph categorize module175. The application graph categorize module retrieves a predefined set of categories for applications from the application graph database185. Examples of predefined categories include sports applications, fitness applications, news applications and the like. Optionally, for each predefined category, each of the inferred signals for an application is assigned a static weight. For each account holder, a linear combination of weights of a predefined category is calculated for every application. Based on the numerical score of each application of the account holder for the predefined category, the category is tagged to the account holder data set. For example, for a fitness category, each signal such as the keywords, active application time, usage time and description may be given a static weight, e.g. (1, 1, 1, 1). Further, by way of example, if a “fitbit” and a “weight watchers” application information is received for an account holder, the values for each of the signals indicate (1, 1, 1, 1) for “fitbit” and (1.0, 0.2, 0.1, 0.5) for “weight watchers”. Based on the values of the signals and the weights, both the applications can be categorized as fitness applications. The account holder data set is tagged with the predefined category fitness.

The application graph for each account holder includes account holder identification (generally termed as account holder id) and an associated list of predefined categories (these are the categories that the account holder is interested inferred based on the application information of the account holder). These application graphs for the account holders are stored in the application graph database185.

Optionally, the application graph builder190may build the application graph at predefined times (e.g., at 10 AM, 2 PM and 5 PM), predefined time periods (e.g. every hour or every 24 hours), or in response to a request from the spam detection module150or the content recommendation module180.

Spam Detection Module

The spam detection module150includes a similar application graph determination module250and a notification module270. The spam detection module150may receive a request to detect a spam application or may periodically check for spam applications. In response to the request, the spam detection module150requests the application graph module190to build an application graph for the client device of each account holder.

The application graph for each account holder is sent to the similar application graph determination module250. The similar application graph determination module250retrieves a set of previously detected and tagged spam application graphs from the application graph database and compares it to the received application graph. A spam application graph is an application graph of an account holder that may be previously detected to be a spammer, for example, the spammer may be a robot application that has a single application installed (e.g., an application that clicks on targeted ads). The example spammer does not download any other applications on its client device. The application graph of such an account holder may include a single application and the usage time for the application may be 100%. Such application graphs are detected and tagged as spam and are stored in the application graph database185.

If the received application graph matches any one of the application graphs associated with a spammer (spam application graph), the received application is tagged as a spam as well and stored in the application graph database185.

If the received application graph is very similar (e.g. 80% comparison match, could be programmatically set to N % comparison match) to one or more spam application graphs, additional information signals such as number of downloads of applications in a time in history, usage time for applications and other such signals are retrieved from the application graph database185. Based on these additional information signals, it may be determined that the received application graph is a spam application or a spam account holder. For example, it may be determined from the additional information signals that a spam account holder has not downloaded applications on their client device for a long time or the usage time for applications other than a spam application, may be minimal, or messages of abusive nature may be detected, that were sent from the client device of the spammer.

If the received application graph does not match the spam application graphs, the similar application determination graph module250searches for a set of similar application graphs from the application graph database185that may not be tagged as spam. If a set of similar applications is found, the similarity may be based on a similarity score (e.g. 80% match of each application category on the application graph, could be programmatically set to N % comparison match), the received application graph is as not a spam. If there are no similar application graphs found, additional information signals such as number of downloads of applications in a time in history, usage time for applications and other such signals are retrieved from the application graph database185. Based on these additional information signals, it may be determined that the received application graph is a spam application.

On determination of a spam application, the notification module270may notify a set of account holders or a set of other applications on one or more client devices about the spam application. Additionally, a set of advertising networks or third party agencies that may have requested information on spam applications may be notified as well. The notification may be sent via electronic communication such as email, messages, tweets, push notifications or other similar methods.

Referring now toFIG. 3, is a method for building an application graph to detect spam applications and notifying a plurality of other applications by the spam detection module, according to one example embodiment. The spam detection module150receives301a request to determine a spam application. In response to the request, the spam detection module150sends (or transmits)303a request to the application graph builder190. The application graph builder190generates an application graph for the client device110of each account holder and store the built application graph in the application graph database185.

The spam detection module150retrieves309, from the database, a set of previously detected spam application graphs. The spam detection module150matches311the generated application graph of each account holder with the retrieved set of previously detected spam application graphs. If a match is detected, the matched application graph is identified317and added to the list of detected spam application graphs.

If a match is not found, the spam detection module150searches313the application graph database185for a set of similar application graphs. It is noted that in one example embodiment a similar application graph is an application graph that matches N % (e.g. 80%) when compared to the generated application graph. If a similar application graph is found315, the generated application graph of the account holder is not identified316as a spam.

If no similar application graphs are found315for an account holder, the generated application graph account holder or the application is labelled317as spam and added to the list of detected spam application graphs in the application graph database185. The determination result, which includes a list of spam applications, if any are found, is sent319to the requestor (e.g. third party applications, ad networks, application developers, etc.) in response to the request. Additionally, other applications or account holders of client devices may be notified of spam applications or account holders by way of electronic communication such as electronic mail (email), tweets, push notification, or messages.

Content Recommendation Module

Referring back toFIG. 2, the content recommendation module180may receive a request to recommend content for a set of account holders, or to recommend account holders for an application of a predefined category. Alternatively, the content recommendation module180may periodically recommend content to account holders based on their application graphs.

The content recommendation module180includes a prediction module210and a recommendation module220. The prediction module210predicts if an account holder would prefer to receive recommendations related to an application of one of a predefined categories based on the application graph for the account holder. For each of the categories, the prediction module210retrieves from the application graph database185, a set of account holders and their application graphs. It is noted that the preference of the account holder for the subject category is unknown at this time of retrieval. Based on the retrieved data, the prediction module210predicts the preference of each account holder using a computer model that applies a machine learning method such as logistic regression or other such similar algorithm. Accordingly, the preference of each of the set of account holders for each category is predicted.

Prediction Model Example

FIG. 4is a block diagram of the logical components of a prediction module for recommending account holders for an application category, according to one example embodiment. The prediction module210includes a training module420, a loss estimation and update module430and a precision and recall calculation module440. The training module420receives an application of a predefined category and a set of account holders that have an unknown preference for the predefined category and the application graph for the set of account holders.

The training module420further retrieves by querying the application graph database185a set of positive samples405and a set of negative samples for a predefined category. The positive samples include a set of account holders that prefer the predefined category and the negative samples include a set of account holders that do not prefer the predefined category. The corresponding application graphs G(g1. . . gn) of the positive and negative samples are retrieved from the database. It is noted that g1. . . gnrepresents features of an application graph for a predefined category. For example, the data associated with a fitness category may include number of fitness applications r1, usage time of the fitness applications r2, number of weight training applications r3, number of outdoor activity applications and other such data.

The features g1. . . gnof the application graphs G are initialized with a weight wr1. . . wrnequal to 1. The weight for each feature of the application graphs G is non-negative and is maintained by the training module420. The training module420further receives training values {y1. . . yn} for {g1. . . gn} from the retrieved application graphs G. The training module420identifies a set of account holders that are likely to prefer an application of a predefined category based on a function that applies logistic regression method (e.g. sigmoid function) based on the weights (wr1. . . wrn) and values (y1. . . yn) of the features of the application graphs G and a threshold n that represents the classification boundary for prediction. The function may be represented as:
h(x)=g(ƒ(x))
where ƒ(x)=wr0+Σj=1nwrj·yrj
and g(f(x)) represents the sigmoid function. The sigmoid function transforms the value of f(x) into the range between 0 and 1. Further, the classification boundary for prediction is given by:

If h(x)>n; then predict1; else predict0, where n ranges from 0 to 1.

The following example provides additional details for the prediction. In this example, the predefined category is fitness. The initial weights (wr1, wr2, wr3) will be (1,1,1) for features (g1,g2,g3). Further, let's assume a training data set is of the format, (y1,y2,y3)->X where X represents the actual value of the preference of the positive account holders for the predefined category. Let's assume the values retrieved from the database for y1, y2, y3and X are (20,20,10)->1. The values indicate an average value of the set of account holders representing the positive samples, i.e. 20 account holders had fitness applications on their list, 20 account holders had weight watcher applications on their list, etc. In this example, f(x) is 50, and let h(x)=0.5 i.e., the predicted value is 0.5 which is close to the classification boundary, and hence a prediction of 1. A prediction is similarly made for each account holder with an unknown preference for the predefined category at the time of retrieval from the application graph database185.

The loss estimation module430receives an actual list of account holders from the actual values module450that preferred an application of a subject category. The training module420is updated based on a weight update function β derived from the confidence of the prediction of the list of the account holders for a predefined category when compared to the actual list of account holders that preferred the predefined category. The weight update function β implies a measure how well the training module420identified the set of account holders that would prefer applications of a predefined category.

The weight update function β is as follows:
β=−log(h(x)) ifX=1
β=−log(1−h(x)) ifX=0

For a predefined category, assume an account holder has a prediction X=1, with a confidence value h(x)=0.6. The confidence value indicates that the account holder has a high probability of preferring content from the predefined category. The actual value received for the same account holder is X=0, i.e. the account holder does not prefer content relevant to the predefined category. The confidence value was higher by an amount of 0.6 indicating a low confidence prediction. Hence the weight updated function demotes the weights related to the prediction by a value α. Alternatively, if the confidence value was around 0.2 indicating a high confidence prediction, the weight updated function promotes the weights related to the prediction by a value α such that the prediction is at an exact value of 0. If the account holder has an exact confidence value such as 1.0 and the actual value indicates X=1 as well, the weights are not adjusted.

Based on the predictions for each category, in one example embodiment two metrics are further calculated. Specifically, the precision and recall calculation module440calculates the precision metric and the recall metric. The precision metric for a category is a measure of how many selected account holders are relevant for the predefined category and the recall metric is a measure of how many relevant account holders were selected for the predefined category. The prediction module210is trained to achieve a predetermined value of precision and recall for each predefined category, for example 70% of precision and recall for all categories. The metrics are calculated as follows:

Referring back toFIG. 2, the recommendation module220receives the prediction results for each predefined categories for each account holder. The recommendation module220may recommend content such as application, advertisements, messages to the account holder based on the predicted results or an application of a predefined category may request for recommendation of account holders that would prefer the application.

Referring now toFIG. 5, shown is a flowchart of a method for building an application graph to recommend content of predefined category to account holders, according to one example embodiment. The content recommendation module180receives501information for one or more applications executing on a client device used by one or more account holders. The content recommendation module180further requests505the application graph builder190to generate an application graph for each of the account holders. The application graph includes the account holder id and a list of predefined categories determined based on the received application information. The content recommendation module may receive a request from an application of a predefined category to recommend account holders for the application.

For each predefined categories, a preference of an account holder for a predefined category is determined511, by accessing509a set of model parameters that comprise of a set of previously determined positive and negative account holders for each category. Based on the determination (by way of calculating the numerical likelihood of a user preference for a predefined category), an account holder is recommended content related to the predefined category.

Example Machine Architecture

FIG. 6is a block diagram illustrating components of an example machine (or device) able to read instructions from a machine-readable medium and execute them in a processor (or controller), such as by a processor of client device110, identity server130, or application server150. Specifically,FIG. 6shows a diagrammatic representation of a machine in the example form of a computer system600. The computer system600can be used to execute instructions624(e.g., program code or software) for causing the machine to perform any one or more of the methodologies (or processes) described herein, for example with respect toFIGS. 1-3. In alternative embodiments, the machine operates as a standalone device or a connected (e.g., networked) device that connects to other machines. In a networked deployment, the machine may operate in the capacity of a server machine or a client machine in a server-client network environment, or as a peer machine in a peer-to-peer (or distributed) network environment.

The example computer system600includes one or more processing units (generally processor602). The processor602is, for example, a central processing unit (CPU), a graphics processing unit (GPU), a digital signal processor (DSP), a controller, a state machine, one or more application specific integrated circuits (ASICs), one or more radio-frequency integrated circuits (RFICs), or any combination of these. The computer system600also includes a main memory604. The computer system may include a storage unit616. The processor602, memory604and the storage unit616communicate via a bus608.

In addition, the computer system606can include a static memory606, a display driver140(e.g., to drive a plasma display panel (PDP), a liquid crystal display (LCD), or a projector). The computer system600may also include alphanumeric input device642(e.g., a keyboard), a cursor control device614(e.g., a mouse, a trackball, a joystick, a motion sensor, or other pointing instrument), a signal generation device618(e.g., a speaker), and a network interface device620, which also are configured to communicate via the bus608.

The storage unit616includes a machine-readable medium622on which is stored instructions624(e.g., software) embodying any one or more of the methodologies or functions described herein. The instructions624may also reside, completely or at least partially, within the main memory604or within the processor602(e.g., within a processor's cache memory) during execution thereof by the computer system600, the main memory604and the processor602also constituting machine-readable media. The instructions624may be transmitted or received over a network626via the network interface device620.

Additional Considerations

Example benefits and advantages of the disclosed configurations include recommending content relevant to a predefined category to an account holder based on their preference for the predefined category. The content recommendation is based on application graphs generated for each account holder. Alternatively, the application graphs can be useful for determination of spam applications or spam account holders in the system. Further, a set of third-party applications, an ad network or application developers can be notified of these spam application or spam account holders.

Upon reading this disclosure, those of skill in the art will appreciate still additional alternative structural and functional designs for a system and a process for recommending content or detection spam applications based on application graphs built for account holders, through the disclosed principles herein. Thus, while particular embodiments and applications have been illustrated and described, it is to be understood that the disclosed embodiments are not limited to the precise construction and components disclosed herein. Various modifications, changes and variations, which will be apparent to those skilled in the art, may be made in the arrangement, operation and details of the method and apparatus disclosed herein without departing from the spirit and scope defined in the appended claims.