Note: Descriptions are shown in the official language in which they were submitted.
CA 02740499 2011-05-17
METHODS, APPARATUS, AND ARTICLES OF MANUFACTURE TO RANK
USERS IN AN ONLINE SOCIAL NETWORK
FIELD OF THE DISCLOSURE
[0001] This disclosure relates generally to measuring social networking
and, more
particularly, to methods, apparatus, and articles of manufacture to rank users
in an online
social network.
BACKGROUND
[0002] Social networking has expanded to the online world and enabled more
people
to stay in contact with larger numbers of personal contacts over great
distances. Some
social networking web sites allow members to create their own websites,
complete with
member-provided profile information and ways to contact the member. Social
networking web sites keep track of a member's list of contacts, which may be
browsed by
the member and/or easily recalled via searching the list of contacts. In
general, social
networking may result in much larger networks of contacts for some users than
was
previously manageable.
BRIEF DESCRIPTION OF THE DRAWINGS
[0003] FIG. 1 illustrates an example computer network to implement an
online social
networking website.
[0004] FIG. 2 is a more detailed block diagram of the example social
networking
monitor of FIG. I.
[0005] FIG. 3 illustrates an example social network for a user on an online
social
networking site.
[0006] FIG. 4 illustrates an example social networking webpage including
interactions
between users and responses to the interactions.
-1-
CA 02740499 2011-05-17
100071 FIG. 5A illustrates an example relational matrix representative of
the
interactions of FIG. 4.
[0008] FIG. 5B illustrates another example relational matrix representative
of the
interaction of FIG. 4 where a friend of the user has restricted a connection
with the user.
[0009] FIG. 6 illustrates example vectors representative of the
interactions of FIG. 4.
[0010] FIG. 7 illustrates an example social networking webpage including a
personal
message sent from one user to another user.
[0011] FIG. 8 illustrates an example relational matrix representative of
the interaction
of FIG. 7.
[0012] FIG. 9 illustrates an example social networking webpage including an
image
and an interaction between users associated with the image.
[0013] FIG. 10 illustrates an example relational matrix representative of
the
interaction of FIG. 9.
[0014] FIG. 11 is a flowchart representative of example machine readable
instructions
which may be executed to identify popular participants in an online social
network.
[0015] FIG. 12 is a flowchart representative of example machine readable
instructions
which may be executed to process interactions.
[0016] FIG. 13 is a flowchart representative of example machine readable
instructions
which may be executed to determine connectedness scores of users on a social
networking site.
[0017] FIG. 14 is a flowchart representative of example machine readable
instructions
which may be executed to determine an interactivity score of a user on a
social
networking site.
-2-
CA 02740499 2011-05-17
[0018] FIG. 15 is a flowchart representative of example machine readable
instructions
which may be executed to determine a rank of a user on a social networking
site.
[0019] FIG. 16 is a flowchart representative of example machine readable
instructions
which may be executed to determine a network efficacy score.
[0020] FIG. 17 is a flowchart representative of example machine readable
instructions
which may be executed to determine a network constancy score of a social
networking
site.
[0021] FIG. 18 is a diagram of an example processor system that may be used
to
execute the example machine readable instructions of FIGS. 11-17 to implement
the
social networking monitor of FIG. 2.
DETAILED DESCRIPTION
[0022] Although the example systems described herein include, among other
components, software executed on hardware, such description is merely
illustrative and
should not be considered as limiting. For example, it is contemplated that any
or all of
the disclosed hardware and/or software components could be embodied
exclusively in
dedicated hardware, exclusively in software, exclusively in firmware or in
some
combination of hardware, firmware, and/or software.
[0023] The example systems, methods, and articles of manufacture described
herein
may be used to identify popular or influential participants on an online
social networking
website (also referred to as a social networking site, or SNS), such as
Facebook ,
Orkut0, MySpace0, Flickrt, etc. In particular, the example systems, methods,
and
articles of manufacture described below may be used to facilitate marketing
products and
services more effectively by identifying users on a social networking site who
may result
-3-
CA 02740499 2011-05-17
in higher advertisement conversion rates (e.g., sales per advertisement view)
and, thus, a
better return on marketing investment. The example systems, methods, and
articles of
manufacture described below may also be used to identify popular participants
in other
types of online interaction applications such as electronic mail (email),
weblogs, and/or
other types of user-generated content web sites.
100241 In general, social network analysis refers to mapping and/or
measuring the
connections and/or relationships between entities (e.g., individuals, groups,
organizations). Social network analysis may measure social network activity by
determining which individuals are directly connected and then determining how
many
direct connections one individual is removed from another individual. For
example, if
individual A is a friend of a friend C of individual B (and is not a direct
friend or contact
of B), A and B are separated by two degrees (e.g., a first link (degree)
between A and an
intermediate friend C and a second link (degree) between the intermediate
friend C and
B). An opinion leader in social networking refers to a person who is highly
influential in
a local network. Such a person is someone whom others may seek out for advice
and/or
information. Similarly, on social networking sites where networks may be much
more
geographically widespread than, for example, local networks, some users of a
social
networking site may have more connections than other users. Thus, some
examples
systems, methods, and articles of manufacture disclosed herein measure direct
and/or
indirect connections of a user on a social networking site and generate a
connectedness
score representative of a user's connectedness. In some examples, the
connectedness
score is based on a rank of the user with other users.
-4-
CA 02740499 2011-05-17
[0025] Some example systems, methods, and articles of manufacture disclosed
herein
identify the more popular and/or influential users on an online social
networking site. In
online social networking, some particular users may have a high number of
connections.
As used herein, the term "user" may refer to an individual, group,
organization, business,
governmental unit, and/or any other real or fictitious unit or entity that may
be
represented in social networking. In some examples, a connection identifier
determines a
number of connections for a specified user. In some examples, the number of
connections is a sum of first-degree, second-degree, and/or third-degree
connections.
The example connection identifier may further determine a number of the
connections
that are restricted and may decrease the value of restricted connections. A
restricted
connection refers to a connection (direct or indirect) between individuals
where at least
one of the individuals has chosen to block some or all types of communications
between
the individuals. For example, if one of the individuals declines to be updated
with the
other individual's status, the connection may be considered restricted.
[0026] The interactivity of a user refers to the number of interactions
between the user
and the contacts, connections, and/or friends of the user occurring on a
social networking
site. An interaction may be any form of activity taking place on a social
networking site
and/or any response to an activity on a social networking site, including but
not limited
to: posting to a wall (e.g., a public or semi-public posting board belonging
to a user to
which anyone with the proper permissions may write or post); sending private
messages;
chatting; viewing or posting images, videos, and/or other media; commenting on
another
user's posted status; viewing the friends of a user; notifications of user
status updates;
and/or posting the results of an application (e.g., event invitations, game
scores, etc.). An
-5-
CA 02740499 2011-05-17
interactivity score of a user is a normalized and/or ranked score based on the
interactivity
of a user compared to the interactivities of other users on the social
networking site.
[0027] Further, in general some users tend to have a higher level of
activity and/or
interactivity on the social networking site. Due to the highly interactive
nature of social
networking sites, activity by a user is often in the form of interaction
(e.g., messaging a
community, to and/or from one or more other entities) with other users. In
some
examples, an interactivity monitor determines a level of interactivity of a
user on the
social networking site. Interactivity may refer to any type of interactivity
between a user
and one or more of the user's direct and/or indirect connections. As used
herein, each
action in a social transaction is an interaction. Thus, a uni-directional
action (e.g., an
action from user A to user B) has one interaction, a bi-directional
transaction has two
interactions (e.g., an action from A to B is a first interaction and a
response from B to A
is a second interaction), and a multi-directional interaction includes 3 or
more
interactions. In some examples, the interactivity monitor counts each
interaction between
users. Thus, for example, an interaction from a user directed at 10 other
users counts as
interactions. In some examples the interactivity monitor counts responses to
an
interaction by generating a data structure (e.g., a relational matrix, a
vector) for the
interaction and updating the data structure to count one or more response
interactions
after they are performed.
[0028] In some examples, a user ranker determines an overall rank of a user
on a
social networking site based on the interactivity of a user and the
connectedness of the
user. The rank of a user may be indicative of the user's popularity on the
social
networking site, because popular users may be more likely to be more connected
with
-6-
CA 02740499 2011-05-17
other users and/or may be more likely to be more active on the social
networking site.
The connectedness of a user refers to the weighted or unweighted number of
users to
which the user is directly or indirectly connected, whereas the connectedness
score is a
normalized or ranked (e.g., percentile ranked) score based on the
connectedness of the
user compared to the connectedness of other users. In some examples, the
interactivity
and/or the connectedness of the user are converted into scores. Example scores
include a
percentile rank of the user for the interactivity of the user and a percentile
rank of the user
for connectedness. In some examples, the interactivity score and the
connectedness score
are weighted equally to determine an overall (e.g., composite) user rank. In
other
examples the interactivity score and the connectedness score are weighted
differently and
then combined to determine the overall (e.g., composite) rank. For example, a
first user
with a relatively high interactivity score and a relatively low connectedness
score and/or a
second user with a relatively low interactivity score and a relatively high
connectedness
score may both be ranked lower than a third user having a high interactivity
score and a
high connectedness score.
[0029] Some example systems, methods, and articles of manufacture described
herein
may employ the user rank to select advertisements for presentation to the
corresponding
user and/or to associate with views of a user's profile by other users.
Instead of being
used to select advertisements directly, the ranks can be provided by the
entity
determining the rank in a report to advertisers. The advertisers may then use
the rank
alone or in combination with other data to select advertisements. In some
examples, an
advertiser may identify and/or select users based on the user interactivity
score, the user
connectedness score, and/or the overall user rank. In some examples, the
identified
-7-
CA 02740499 2011-05-17
user(s) may be propositioned to endorse and/or otherwise associate with the
advertiser's
product(s) and/or service(s).
[0030] In some examples, the connectedness score(s), the interactivity
score(s), and/or
the ranking may be used as a measure of efficacy of an online social
networking site. In
some examples, a user's score(s) and/or overall rank may be presented to the
user to
inform him or her of the same. For example, some users may perceive a
challenge to
increase their score(s) and/or to improve their ranking(s), thereby
potentially increasing
the usage of the site by some users. User exposure to advertising may be
affected by
usage of the site and, therefore, increased usage of the site by users may
increase the
advertising exposure by those users and generate increased revenue to the
site. The
network efficacy score may also allow a social networking site to evaluate its
advertising
pricing structure to reflect a marketing appeal of the social networking site
to advertisers.
[0031] FIG. 1 illustrates an example computer network 100 to implement an
online
social networking site 102. The network 100 includes a host server 104 that
may be
implemented, for example, using web hosting servers and/or software. The host
server
104 is connected via a wide area network 106, such as the Internet, to other
computers
108 and 110 and/or social networking monitor(s) 112. The computers 108 and 110
may
be employed by users of the social networking site 102 (or others) to view a
web page
114 via web browser application(s) (e.g., Microsoft's Internet Explorer web
browser)
executed on the computers 108 and 110. Upon receiving a request from the
computer
108 or 110 via the wide area network 106, the example host server 104
retrieves data
corresponding to the request and transmits data representing the requested web
page 114
to the requesting computer 108, 110. The host server 104 may further receive
messages
-8-
CA 02740499 2011-05-17
from users of the computers 108 and 110 that include requests for information
associated
with one or more interactions between users and/or between a user and the
social
networking site 102. Example interactions include, but are not limited to,
posting content
to a wall (e.g., a public or semi-public posting board belonging to a user to
which anyone
with the proper permissions may write or post); sending private messages;
chatting;
viewing or posting images, videos, and/or other media; commenting on a user's
status;
viewing the friends of a user; notifications of user status updates; and/or
posting the
results of an application (e.g., event invitations, game scores, etc.).
[0032] The example social networking monitor 112 of FIG. 1 also accesses
the social
networking site 102 via the wide area network 106. Alternatively, the monitor
112 may
be directly connected to, or integrated within, the social networking site
102. In some
examples, the social networking site 102 provides one or more application
program
interfaces (APIs) that allow the social networking monitor 112 to access data
contained
on the social networking site 102 that is provided by users. The social
networking
monitor 112 may be accessed by a monitor terminal 116 that is remote from the
social
networking monitor 112. For example, a client (e.g., an advertiser) may use
the social
networking monitor 112 to identify one or more users of the social networking
site 102
based on the connectedness and/or the interactivity of the user(s) by
accessing the social
networking monitor 112 and/or submitting a request via the monitor terminal
116. The
monitor terminal 116 may be directly connected 120 to the social networking
monitor
112 and/or indirectly connected 122 to the monitor terminal (e.g., via the
wide area
network 106).
-9-
CA 02740499 2011-05-17
[0033] In the example of FIG. 1, the social networking monitor 112
periodically
and/or aperiodically queries the social networking site 102 to determine an
overall rank,
an interactivity score and/or a connectedness score of one or more users of
the social
networking site 102. For example, the social networking monitor 112 may
collect data
from the social networking site 102, analyze the collected data, and update a
database 118
that includes an identification, an interactivity, an interactivity score, a
connectedness, a
connectedness score, and/or a rank (e.g., an overall rank among users of the
social
networking site 102) for one or more of the social networking users. The
example
database 118 of FIG. 1 associates the identification of a user with his or her
respective
interactivity score, connectedness score, and/or rank(s). The database 118 may
additionally or alternatively store the analyzed interactivity data and/or
connectedness
data for the users. When the social networking monitor 112 identifies a new
user on the
social networking site 102, the social networking monitor 112 generates a new
entry in
the database 118 corresponding to the user and populates the respective fields
with the
interactivity score(s), connectedness score(s), and/or rank(s).
[0034] FIG. 2 is a more detailed block diagram of the example social
networking
monitor 112 of FIG. 1. The example social networking monitor 112 of FIG. 2
receives a
request for identification of one or more listings of users of the social
networking site 102
(FIG. 1) based on one or more criteria. The monitor 112 ranks the users of the
social
networking site 102 based on the received criteria, and provides one or more
lists
identifying the ranked users and/or corresponding user information to the
requester. To
this end, the example social networking monitor 112 of FIG. 2 includes a user
selector
202, a connectedness monitor 204, an interactivity monitor 206, and a user
ranker 208.
-10-
CA 02740499 2011-05-17
The example social networking monitor 112 is further shown as including the
database
118 of FIG. 1. However, the database 118 may be external to and in
communication with
the social networking monitor 112.
[0035] The example user selector 202 receives a user request query 210
(e.g., from the
monitor terminal 116 of FIG. 1). The user request query 210 may include a
request for
one or more of, for example, a connectedness of one or more users, a
connectedness score
of one or more users, an interactivity of one or more users, an interactivity
score of one or
more users, an overall rank of one or more users, and/or a list of users
and/or traits (e.g.,
demographic profile, personal social networking site activity, etc.) of users
having
specified connectedness, connectedness scores, interactivity, interactivity
scores, and/or
ranks. Additional traits of users may be obtained via, for example, processing
profile
information provided to the social networking site 102 by users, screen
scraping publicly
available information from user profiles, and/or using other methods of
determining user
traits.
[0036] The user selector 202 interprets the user request query 210 and,
based on the
query 210, determines which of the connectedness monitor 204 and/or the
interactivity
monitor 206 are to generate data and/or retrieve previously generated data
from the
database 118. In general, the connectedness monitor 204 determines a number of
users to
which each user is directly and/or indirectly connected via the social
networking site 102.
The connectedness monitor 204 then determines a connectedness and a
connectedness
score of a user. A more detailed description of the operation of the
connectedness
monitor 204 is provided below with reference to FIG. 3.
-11-
CA 02740499 2011-05-17
[0037] FIG. 3 illustrates an example social network 300 for a user 302 on
the social
networking site 102 of FIG. 1. The illustrated social network 300 is focused
on the
particular user 302 and the connections between other users 304, 306, 308 and
the user
302. In the example of FIG. 3, first-degree, or direct, connections are
labeled with
reference numeral 304, second-degree connections (e.g., friend-of-a-friend)
are labeled
with reference numeral 306, and third-degree connections (e.g., friend-of-a-
friend-of-a-
friend) are labeled with reference numeral 308. The user 304d is also directly
connected
to both users 304b and 304c as represented by the dashed lines in FIG. 3. Some
connections may be made through multiple channels. For example, if the user
302 was
not a direct connection with the user 304b, the user 302 would be a second-
degree
connection to the user 304b through the user 304d. In some examples the
connectedness
monitor 204 ignores the connections between two users other than the closest
or shortest
connection.
[0038] The example connectedness monitor 204 of FIG. 2 may weight the first-
degree
connections 304a-304d, the second-degree connections 306, and the third-degree
connections 308 differently. For example, a second-degree connection 306 may
be
considered less of a connection than a first-degree connection 304a-304d.
[0039] For an example person i (e.g., the user 302), Equation 1 shows a
number of
contacts Mi including both direct and indirect contacts. In Equation 1, Di is
the number
of direct contacts of the user 302, I2i is the number of second-degree
contacts of the user
302, I3i is the number of third-degree contacts of the user 302, and INi is
the number of
Nth-degree contacts of the user 302.
[0040] Mi = Di + I2i + I3i + ...+ INi Eq. 1
-12-
CA 02740499 2011-05-17
[0041] In some examples, the numbers of indirect contacts 12i-INi exclude
any
persons that are connected to the user 302 through a closer degree of
connection. For
example, the 121 indirect contacts (e.g., the users 306) may exclude any of
the direct
contacts (e.g., the users 304a-304d) of the user 302 because, as described
above, some
contacts 304a-304d, 306, 308 may be connected to the user 302 through multiple
paths.
Similarly, the I3i indirect contacts may exclude any of the direct contacts
304a-304d
and/or the second-degree contacts 306 of the user 302, and so on up to the INi
Nth-degree
contacts. However, in some examples the indirect contacts 12i-INi may include
all
contacts that may be reached through the respective numbers of degrees to, for
example,
increase the connectedness scores of those users who have more interconnected
networks
of contacts.
[0042] The connectedness monitor 204 determines a connectedness Ci based on
the
direct and indirect contacts of the user 302. The example connectedness
monitor 204
assigns different weights to the direct contacts Di and the indirect contacts
I2i-INi based
on the number of steps between the level (e.g., second-degree, third-degree,
etc.) of
connection and the user 302. Equation 2 is an example of a connectedness Ci
for the user
302, where N is the number of degrees or steps between the user 302 and the
Nth-degree
contacts.
[0043] Ci = Di + (12i 12) + (13i 13) + + (INi I N) Eq. 2
[0044] The example connectedness score of Equation 2 may assume that all
participants of the network (e.g., the direct contacts Di and the indirect
contacts 12i-INi)
are given full or substantially full access to the user 302 (e.g., the ability
to view and/or
contact the user 302) and/or to other users 304a-304d, 306, and 308 of the
social
-13-
CA 02740499 2011-05-17
networking site 102. However, some social networking sites allow the users 302-
308 to
control the access given to the other users 302-308 on the social networking
site 102. In
some examples, users 304-308 that have restricted connections with the user
302 are
removed from the corresponding contact count Di, I2i, I3i, or INi. However, in
some
examples the users 304-308 that have restricted connections with the user 302
are not
removed but instead are weighted lower than users 304-308 that have full
connections
with the user 302. For example, Equation 3 illustrates a connectedness
Cirernove where the
users 304-308 who have a restricted connection with the user 302 are removed,
and
Equation 4 illustrates a connectedness Ciweight having some restricted
connections DRi,
I2Ri, I3Ri, and INRi have a reduced weight relative to respective ones of the
unrestricted
connection counts DUi, IU2i, IU3i, and IUNi. In some examples, the
connectedness
monitor 204 establishes an upper limit on the number of degrees N to be
counted, where
all connections more than N steps are ignored. In some other examples, the
connectedness monitor 204 does not limit the upper value of N.
Ci remove = {Di + (I2i I 2) + (130 3) + ...+ (INi I N)}
[0045] Eq. 3
¨{DRi +(12i/ 2) + (13i1 3) + I N)}
Ci.e,0õ= {DM + (IU2i I2)+ (IU3i 13) +...+ (IUNil N)}
[0046] Eq. 4
+ 0.001* {DRi+ (IR2i I 2) (1R3i13)+ ...+(IRNil N)}
[0047] In some examples, the weight factor (e.g., 0.001 in Equation 4)
applied to the
restricted connections DRi, IR2i, IR3i, and IRNi may be based on the
activities or
interactions in which the user 302 engages and the notifications that the user
302 or the
user 304, 306, or 308 has chosen to restrict. Example interactions that may be
blocked
include, but are not limited to, posting to a wall (e.g., a public or semi-
public posting
board belonging to a user to which anyone with the proper permissions may
write or
-14-
CA 02740499 2011-05-17
post); sending private messages; chatting; viewing or posting images, videos,
and/or other
media; commenting on a user's status; viewing the friends of a user;
notifications of user
status updates; and posting the results of an application (e.g., event
invitations, game
scores, etc.). In some examples, activities in which the user 302 engages
longer or more
often are weighted higher than activities in which the user 302 engages less
often when
such activities are restricted between the user 302 and other users 304-308,
and
connections that are completely restricted may be weighted highest (i.e., to
reduce the
amount the connection counts toward the connection score the most of any
weight).
Thus, the example equations 2-4 may be modified to apply multiple weights
according to
different restriction combinations.
[0048] Many of the interactions may be restricted either by the originating
(performing, initiating) user 302 or by the receiving user 304, 306, or 308.
Thus, DRi
may be the sum of those users 304a-304d to whom the user 302 has restricted
viewing the
user's 302 activities, those users 304-308 whose activities the user 302 has
chosen not to
view, those users 304-308 who have blocked the user 302 from viewing their
activities,
those users 304-308 who have chosen to view less of the user's 302 activities,
and/or any
other blocking or ignoring options.
[0049] After determining a connectedness (e.g., Ciweight or Ci
-remove), the example
connectedness monitor 204 may make the connectedness of the users 302-308 more
comparable by generating a connectedness score (e.g., assigning the user 302 a
percentile
rank). Equation 5 illustrates an example percentile formula that may be used
to
determine the percentile rank of a user 302 with respect to his or her
connectedness for
use as a connectedness score. In Equation 5, X is the number of users 302-308
whose
-15-
CA 02740499 2011-05-17
connectedness are less than Ci (e.g., Ciweight or Ci
-remove), Y is the total number of unique
users in the social networking site 102, and P(Ci) is the percentile of the
connectedness
Ci. The example connectedness Ci and the connectedness score (e.g., percentile
P(Ci))
may be updated regularly or irregularly because the connections in a social
networking
site change frequently.
[0050] P(Ci) (X I Y)*100 Eq. 5
[0051] Returning to FIG. 2, after determining the connectedness and/or the
connectedness score(s) of one or more users, the connectedness monitor 204
provides the
information to the user ranker 208 and/or to the database 118. The
connectedness
monitor 204 may further determine network constancy score(s) for one or more
users. As
described above, a network constancy score represents the degree to which
removing a
user from the social networking site 102 may reduce the connectedness of the
remaining
users on the social networking site 102.
[0052] In general, the interactivity monitor 206 determines an
interactivity and/or an
interactivity score for one or more users of the social networking site 102.
The
interactivity monitor 206 may determine the interactivity of a user by
determining (e.g.,
counting) a number of interactions between the user and other users on the
social
networking site 102. The interactivity monitor 206 may further convert the
interactivity
into an interactivity score by, for example, comparing the interactivities of
the users of
the social networking site 102. Example determinations of an interactivity
score are
described in more detail below. However, such examples are merely illustrative
and may
be modified based on any one or more of the format, the configuration, the
purpose, the
-16-
CA 02740499 2011-05-17
features, the user population, and/or any other traits of a particular social
networking site,
and/or based on the type of interactions being measured on the social
networking site.
[0053] FIG. 4 illustrates an example social networking webpage 400
including
interactions 402 and 404 between example users 406, 408, 410, and 412 and
response
interactions 414, 416, 418, and 420 to the interactions 402 and 404. The
example
interaction 402 represents, for example, a status update by the user 406, in
which the user
406 posts a message intended to be viewed by any users who are directly
connected (e.g.,
first-degree contacts) and/or indirectly connected (e.g., second-degree
contacts, etc.) to
the user 406. Similar interactions may include posting results from an
application (e.g.,
an online game), updating profile information, posting a link to another
website, and/or
posting media (e.g., music, video, etc).
[0054] On some social networking sites, the connections (e.g., the users
408 and 410)
of the user 406 who posts the status update interaction 402 may respond to the
interaction
with their own respective response interactions 414 and 416. The responses 414
and 416
may be directed to the user 406, the direct connections of the user 406, any
users 408 and
410 who have responded to the interaction 402 to which the response 414 is
directed,
and/or any other users 406-412 who may be updated with the status of the user
406. On
some social networking sites, the ability to notify and update users 408-412
with the
status (or other posting) of the user 406 is practically unlimited. For
example, the user
406 may make his or her profile available to any user 408-412 of the social
networking
site 102 (FIG. 1) who wants to subscribe to or follow the user 406 and/or even
to any
member of the public having access to the wide area network 106 of FIG. 1.
-17-
CA 02740499 2011-05-17
[0055] FIG. 5A illustrates an example relational matrix 500 representative
of the
interactions 402, 414, and 416 of FIG. 4. As described above, a relational
matrix (or a
vector or other data structure) is generated and/or updated for each
interaction 402, 404,
414-420 and/or set of interactions (e.g., the set of interactions 402, 414,
and 416, and the
set of interactions 404, 418, and 420). In the relational matrix 500, the user
406 is
represented as i and has D,x direct contacts. The example user i 406 of FIG.
5A has 11
direct contacts and, therefore, the relational matrix 500 includes contacts
D,1-D,11.
[0056] The columns in the matrix 500 represent the users 406-412 at whom an
interaction 402, 404, or 414-420 is directed, while the rows in the matrix 500
are the
users 406-12 who generate or perform responsive interaction(s) 402, 404, or
414-420. A
first row 502 of the matrix 500 represents the interactions performed by the
user i 406,
including the initial interaction 402 performed by the user i 406. The user
406 (e.g., user
i) posts the interaction 402 (e.g., a status update) for each of his or her
contacts D,1-D,11,
causing the example interactivity monitor 206 (FIG. 2) to enter 1 interaction
count into
each column in the row 502 corresponding to the contacts D,1-D111, for a total
of 11
interaction counts for the interaction 402. The example contacts D,1 and D12
each post a
response (e.g., interactions 414 and 416) to the status update interaction 402
as illustrated
in respective rows 504 and 506. Thus, the interactivity monitor 206 enters 1
interaction
count into the i column 508 in the rows 504 and 506.
[0057] Because the response interactions 414 and 416 may occur some time
after the
interaction 402, the interactivity monitor 206 may store the relational matrix
500 into a
database (e.g., the database 118 of FIG. 1) and retrieve the relational matrix
500 at a later
time for updating. While in the illustrated example the interactivity monitor
206 only
-18-
CA 02740499 2011-05-17
enters interaction counts into the i column 508, the interactivity monitor 206
may
additionally or alternatively enter interaction counts into one or more of the
D,1-D,11
columns to represent interactions by D,1 and/or D,2 with other contacts D,1-
D,11 of the
user i 406. For example, on some social networking sites any user 406-412 who
performs
a response interaction 414 to the initial interaction 402 is notified of later
response
interactions 416 from other users 406-412 to the same initial interaction 402.
Additionally or alternatively, some social networking sites notify a user 406
when a
direct contact (e.g., the user 408) performs an initial and/or response
interaction 402, 404,
or 414-420 to a mutual direct contact (e.g., the user 410). The example
interactivity
monitor 206 may therefore update the relational matrix 500 in accordance with
the
particular notification and/or interaction tools and/or mechanisms of a
particular social
networking site. In some examples, the interactivity monitor 206 also enters
an
interaction count into the Dil column of the Di2 row 506 to indicate that Dil
(e.g., Friend
1 408 of FIG. 4) is also notified because she previously generated the
response interaction
414 and is notified about further response interactions (e.g., 416).
[0058] FIG. 5B illustrates another example relational matrix 510
representative of the
interaction 402 of FIG. 4 where a direct contact D,5 of the user 406 has
restricted or
blocked status update interactions from the user 406. Some social networking
sites
provide their respective users 406-412 options to block notifications about
one or more of
their direct and/or indirect contacts. For example, a user 412 may choose not
to be
notified when the user 406 performs one or more of: posting to a wall; sending
private
messages; chatting; viewing or posting images, videos, and/or other media;
commenting
on a user's status; viewing the friends of a user; notifications of user
status updates;
-19-
CA 02740499 2011-05-17
posting the results of an application (e.g., event invitations, game scores,
etc.); and/or any
other interaction(s) with the social networking site 102. The example
relational matrix
510 of FIG. 5B is representative of the example interaction 402 and the
response
interactions 414 and 416 of FIG. 4, except that the direct contact D15 of the
user 406 has
chosen to ignore or block one or more types of status updates from the user
406, of which
the interaction 402 is one type. The example interactivity monitor 206 of FIG.
2 may
determine notification settings of the direct contacts D,1-Dill of the user
406 and
determine, based on the notification settings, that the contact D15 has
disabled
notifications for status updates (e.g., restricted, ignored, blocked, etc.).
Thus, when the
user i 406 generates the interaction 402 directed at the contacts DJ-DJ 1, the
interactivity
monitor 206 determines that there is no interaction between the user i 406 and
the contact
D,5, and therefore does not enter an interaction count in a column 512
corresponding to
the contact D,5 and a row 514 corresponding to the interaction 402.
[0059] FIG. 6 illustrates example vectors 602-622 representative of the
interactions
402, 414, and 416 of FIG. 4. The example vectors 602-622 may be used as an
alternative
to the example relational matrix 500 illustrated in FIG. 5A to store the
interaction counts
of FIG. 4. In the example of FIG. 6, the interactivity monitor 206 generates a
vector 602-
622 for each connection between the user i 406 and the participants Dil -D, I
1 in the
interaction 402. Each of the vectors 602-622 has a weight that is
representative of the
number of interaction counts between the user i 406 and the corresponding user
D,1-D111.
For example, the vector 602 that includes the user i 406 and the user Dl
(e.g., Friend 1
408) has a weight of 2 because the interaction 402 and the response
interaction 414
include the users 406 and 408. In contrast, the weight of the example vector
606 is 1
-20-
CA 02740499 2011-05-17
because only the interaction 402 includes the user i 406 and the user D,3.
Additionally or
alternatively, the vectors 602 and 604, or the vectors 602-622, may be
bidirectional
vectors that include the interaction counts in a first direction from the user
i 406 to the
respective users 408 and 410 and in a second direction from the respective
users 408 and
410 to the user i 406.
[0060] FIG. 7 illustrates an example social networking webpage 700
including a
personal message interaction 702 sent from a user 406 to another user 408. On
the
example social networking site 102 of FIG. 1, the user 406 may interact with
one or more
other users 408-412 by transmitting a message directly to the other user(s)
408-412. The
receiving user(s) 408-412 may access the message by, for example, navigating
to the
social networking site 102 via a web browser to view the message. The example
message
interaction 702 is directed from the user 406 to the user 408 and to no other
users.
[0061] FIG. 8 illustrates an example relational matrix 800 representative
of the
message interaction 702 of FIG. 7. While the example relational matrix 800
includes all
of the contacts 1)11-D1 1 of the user i 406, the interactivity monitor 206
determines that
the interaction 702 only took place between the users 406 and 408. In some
examples,
however, the relational matrix 700 only includes those contacts D11-D,11 who
are
included in the initial transaction. Thus, the interactivity monitor 206 adds
an interaction
count to the appropriate column 802 and row 804. If the user 408 does not
respond to the
interaction 702 (e.g., by sending a reply message), the example matrix 800 may
be
considered complete, and another relational matrix is created for a later
interaction.
[0062] FIG. 9 illustrates an example social networking webpage 900
including an
image 902 and an interaction 904 between users 406-412 associated with the
image 902.
-21-
CA 02740499 2011-05-17
The example image 902 may be posted by, for example, the user 406, who further
"tags"
the picture with identifications of other users 408, 412, 906, and 908 who are
also present
in the image 902. On some social networking sites (e.g., the social networking
site 102
of FIG. 1), users 406-412, 906, and 908 may post comments 910 and 912 about
the image
902 for others to view when they view the image 902. In the illustrated
example, the
users 406 and 408 have left respective comments 912 and 910 about the image
902.
[0063] FIG. 10 illustrates an example relational matrix 1000 representative
of the
interaction of FIG. 9. The example relational matrix 1000 includes the user i
406 and the
contacts D11-D111 of the user 406. The interactivity monitor 206 (FIG. 2)
determines that
the user i 406 posted the image 902 and tagged the respective users 408, 412,
906, and
908 who are in the image 902. In response, the interactivity monitor 206
enters
interaction counts into a row 1002 corresponding to interactions by the user i
406 directed
at other users 408-412, 906, and 908 within columns corresponding to the
receiving users
of the interaction (e.g., the posting and/or tagging of the image 902).
[0064] The example interactivity monitor 206 further detects the comments
910 and
912 and adds additional interactivity counts to a row 1004 corresponding to
the user D,1
(e.g., Friend] 408) who generated the response interaction 910, and to the row
1002
corresponding to the user i 406 who generated the response interaction 912. In
the
illustrated example, the interactivity monitor 206 only generates an
interaction count for a
response interaction 912 in a column 1006 corresponding to the user D11 408
who
generated the previous response interaction 910. However, the interactivity
monitor 206
may generate interaction counts in any row and/or column based on the
particular
configuration and/or settings of the social networking site (e.g., the social
networking site
-22-
CA 02740499 2011-05-17
102). In general, each social networking site may choose to notify users of
interactions
and/or activities by other users that may potentially be of interest to them
in different
ways. Thus, the interactivity monitor 206 may generate interaction counts
based on the
particular notification settings and/or configurations of the social
networking site 102
and/or the users 406-412, 906, and 908.
[0065] In some examples, the relational matrices 500, 510, 800, and 1000
are used by
the interactivity monitor 206 to determine an interactivity of the user i 406.
The
interactivity for the example user i 406 may be determined by summing the
interaction
counts in the relational matrices corresponding to the user i 406 over a
specified time
period or over all time. In these examples, the interactivity monitor 206
generates similar
relational matrices for the users D,1 -D,1 1 to represent the respective
interaction counts for
use in determining the respective interactivities of the users D,1-D,11. In
some examples,
however, the interactivity monitor 206 uses the relational matrices 500, 510,
800, and
1000 to determine the interactivities for any of the users D11-D111. While
these examples
may result in fewer relational matrices or other data structures to be stored,
the
interactivity monitor 206 may have to search through a larger number of
relational
matrices to determine the interactivity of the user i 406.
[0066] An interactivity score of the user i 406 may be determined by, for
example,
comparing the interactivity of the user i 406 to the interactivities of other
users on the
social networking site. For example, the interactivities may be normalized
based on an
upper interactivity, a lower interactivity, a median interactivity, and/or
another
normalization factor. Additionally or alternatively, the interactivity score
may be
determined based on a percentile rank of the interactivity of the user i 406.
-23-
CA 02740499 2011-05-17
[0067] Additionally or alternatively, any of the relational matrices 500,
510, 800, or
1000 may be represented as a vector or in another data structure format. For
example, the
relational matrix 500 may be represented according to the following vector:
<i; D11,1,1;
D12,1,1; D13,1,0; D,4,1,0; D,5,1,0; D,6,1,0; D,7,1,0; D,8,1,0; D19,1,0;
D,10,1,0; D111,1,0>.
Thus, the example vector identifies the user i 406, the users D,1-D,11, and
the interaction
counts directed at each of the users D,1-D,11 by the user 1406 and the
interaction counts
directed at the user i 406 by each of the users D,1-D,11. Of course, other
vector formats
may be used instead of the example vector or the relational matrices 500, 510,
800, or
1000.
[0068] Returning to FIG. 2, after the interactivity monitor 206 determines
the
interactivities and/or the interactivity scores for the users, the
interactivity monitor 206
provides the interactivities and/or the interactivity scores to the user
ranker 208 and/or to
the database 118. In some examples, the interactivity monitor 206 regularly
processes
interactions (e.g., batch processing) between users of the social networking
site 102 and
stores the resulting generated and/or updated relational matrices and/or
vectors in the
database 118. To this end, a data collection monitor 214 determines whether
data
collection should occur and controls the interactivity monitor 206
accordingly.
Additionally or alternatively, the data collection monitor 214 may control the
connectedness monitor 204 to collect and/or process the connectedness of the
users of the
social networking site 102 at regular and/or irregular intervals.
[0069] The user ranker 208 of FIG. 2 receives the connectedness and/or the
connectedness scores from the connectedness monitor 204 and/or the
interactivities
and/or the interactivity scores from the interactivity monitor 206. Based on
the received
-24-
CA 02740499 2011-05-17
information, the user ranker 208 determines user rank(s) 212 for one or more
users of the
social networking site 102 (e.g., based on the user request query 210). The
user rank(s)
may then be output to the location from which the user request query 210 was
received
(e.g., the monitor terminal 116 of FIG. 1) and/or to a different location
(e.g., a storage
device, a central data facility, an advertiser, database 118).
[0070] The user ranker 208 may generate user rank(s) by, for example,
weighting the
interactivity score and the connectedness score and then combining the
weighted scores
to generate an overall (e.g., composite) rank. The weight(s) applied to the
connectedness
score and/or the interactivity score may be equal or different based on, for
example, the
user request query 210. For example, if an advertiser believes that its
products are more
likely to sell by simply informing users of its products, the user ranker 208
may weight
the connectedness score of the users more heavily than the interactivity
scores.
[0071] The example social networking monitor 112 further includes a network
constancy determiner 216 to determine a network constancy score for one or
more users
in the social networking site 102. The network constancy score for a user is
representative of a number of connections that would be broken, and/or
increased in
degree by more than a threshold number of degrees, if the user was removed
from the
social networking site. The network constancy score may be used by, for
example, an
advertiser or marketer to determine the efficacy of a particular social
networking site.
For example, if a social networking site has users having low networking
constancy
scores relative to other social networking sites, the social networking site
may be
considered less stable because removing users from the social networking site
may also
remove larger numbers of connections, thereby decreasing the connectedness of
the users
-25-
CA 02740499 2011-05-17
on the social networking site. Less stable social networking sites are likely
less desirable
places to purchase advertisements and/or longer running advertising campaigns.
[0072] To determine a network constancy score, the connectedness monitor
204
determines the connections between the user (e.g., the user 302 of FIG. 3) and
the other
users 304-308 to which the user is connected. The network constancy determiner
214
then evaluates the connections between the users 304-308 to determine which of
the users
304-308 would, if the user 302 was removed from the social networking site
102, be
disconnected from each other, be connected to each other at a higher degree of
separation, and/or continue to be connected to each other.
[0073] The network constancy score may be, for example, a proportion of the
users
304-308 who would remain connected within a degree threshold when the user 302
is
removed from the social networking site 302. In some examples, the network
constancy
score may be weighted according to the degree of the connections that are
dropped. For
example, a second-degree connection that is broken may be weighted higher (and
therefore affect the network constancy score more) than a fifth-degree
connection that is
broken.
[0074] In an example, the network constancy determiner 214 may determine a
network constancy score for the user 302 of FIG. 3. By removing the user 302
from the
network, the user 304a is disconnected from the users 304b-304d. However, the
users
304b-304d remain connected. Thus, three second-degree connections (e.g., the
users
302a and 302b, 302a and 302c, and 302a and 302d) are broken while two first-
degree
connections (302b and 302d, and 302c and 302d) and a second-degree connection
(302b
and 302c) remain unbroken. Using the ratio of broken connections up to second-
degree
-26-
CA 02740499 2011-05-17
connections as the example network constancy score, the network constancy
score for the
user 302 is 0.5. However, the network constancy score may use a higher degree
of
connection and/or a ratio of different factors (e.g., users connected or
disconnected).
[0075] The example social networking monitor 112 further includes a network
efficacy determiner 218 to determine a network efficacy score 220. The example
network efficacy determiner 218 determines a network efficacy of the social
networking
site 102 based on an average user connectedness of the users of the social
networking site
102, the average interactivity of the users of the social networking site 102,
and/or the
network constancy scores for the users of the social networking site 102. An
example
determination of network efficacy E is shown in Equation 6 below, where C is
the
average connectedness of the users, I is the average interactivity of the
users, and X is the
average network constancy of the users of the social networking site 102 for
which the a
network efficacy score.
[0076] E = C +1¨ X Eq. 6
[0077] The network efficacy determiner 218 may generate the network
efficacy
score(s) 220 for one or more social networking sites 102 (or other types of
interaction
web sites and/or services such as online messaging) in response to, for
example, a request
from an advertiser. An advertiser may be interested in comparing, for example,
the
network efficacies for multiple social networking sites in which the
advertiser may be
interested in advertising. Additionally or alternatively, the network efficacy
determiner
218 may determine network efficacy score(s) 220 at periodic and/or aperiodic
intervals to
monitor the network efficacy score(s) 220 of social networking sites over
time.
-27-
CA 02740499 2011-05-17
100781 FIGS. 11-17 depict example flow diagrams representative of processes
that
may be implemented using, for example, computer readable instructions that may
be used
to implement the example user selector 202, the example connectedness monitor
204, the
example interactivity monitor 206, the example user ranker 208, the example
data
collection monitor 214, the example network efficacy determiner 218, and/or,
more
generally, the example social networking monitor 112 of FIG. 2. The example
instructions 1100, 1200, 1300, 1400, 1500, 1600, 1700 of FIGS. 11-17 may be
performed
using a processor, a controller and/or any other suitable processing device.
For example,
the example instructions 1100-1700 of FIGS. 11-17 may be implemented using
coded
instructions (e.g., computer readable instructions) stored on a tangible
computer readable
medium such as a flash memory, a read-only memory (ROM), and/or a random-
access
memory (RAM). As used herein, the term tangible computer readable medium is
expressly defined to include any type of computer readable storage and to
exclude
propagating signals. Additionally or alternatively, the example instructions
1100-1700 of
FIGS. 11-17 may be implemented using coded instructions (e.g., computer
readable
instructions) stored on a non-transitory computer readable medium such as a
flash
memory, a read-only memory (ROM), a random-access memory (RAM), a cache, or
any
other storage media in which information is stored for any duration (e.g., for
extended
time periods, permanently, brief instances, for temporarily buffering, and/or
for caching
of the information). As used herein, the term non-transitory computer readable
medium
is expressly defined to include any type of computer readable medium and to
exclude
propagating signals.
-28-
CA 02740499 2011-05-17
[0079] Alternatively, some or all of the example instructions 1100-1700 of
FIGS. 11-
17 may be implemented using any combination(s) of application specific
integrated
circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)), field
programmable logic
device(s) (FPLD(s)), discrete logic, hardware, firmware, etc. Also, some or
all of the
example instructions 1100-1700 of FIGS. 11-17 may be implemented manually or
as any
combination(s) of any of the foregoing techniques, for example, any
combination of
firmware, software, discrete logic and/or hardware. Further, although the
example
instructions 1100-1700 of FIGS. 11-17 are described with reference to the flow
diagrams
of FIGS. 11-17, other methods of implementing the instructions 1100-1700 of
FIGS. 11-
17 may be employed. For example, the order of execution of the blocks may be
changed,
and/or some of the blocks described may be changed, eliminated, sub-divided,
or
combined. Additionally, any or all of the example instructions 1100-1700 of
FIGS. I I -
17 may be performed sequentially and/or in parallel by, for example, separate
processing
threads, processors, devices, discrete logic, circuits, etc.
[0080] FIG. 11 is a flowchart representative of example machine readable
instructions
1100 which may be executed to identify popular participants in an online
social network
(e.g., the social networking site 102 of FIG. 1). The example machine readable
instructions 1100 may be executed by the social network monitor 112 of FIG. 2.
[0081] The example instructions 1100 begin by determining (e.g., via the
data
collection monitor 214 of FIG. 2) whether to collect data (e.g., process
interactions)
(block 1102). For example, the data collection monitor 214 may determine
whether a
data collection period has lapsed. If the data collection monitor 214
determines that it is
time to collect data (block 1102), the example interactivity monitor 206 of
FIG. 2
-29-
CA 02740499 2011-05-17
processes interactions on the social networking site 102 (block 1104). Example
instructions 1200 to implement block 1104 are described below with reference
to FIG.
12. As described above, the data collection monitor 214 may additionally or
alternatively
cause the connectedness monitor 204 to process the connectedness of one or
more users
of the social networking site 102. After processing the interactions (block
1104), or if it
is not time to collect data (block 1102), the user selector 202 of FIG. 2
determines
whether a query has been received (block 1106). If a query has not been
received,
control returns to block 1102 to determine whether it is time to collect data.
[0082] If a query is received (block 1106), the user selector 202 receives
the request,
such as a user request query 210 (FIG. 2) for the popularities of one or more
users of the
social network site 102 (block 1108). The connectedness monitor 204 of FIG. 2
determines one or more connectedness scores for the users based on the user
request
query 210 (block 1110). Block 1110 may be implemented using example machine
readable instructions 1300 described below with reference to FIG. 13. In some
examples,
the determination of the connectedness scores includes determining the
connectedness of
the users. The interactivity monitor 206 determines one or more interactivity
scores for
the users based on the user request query 210 (block 1112). Block 1112 may be
implemented using example machine readable instructions 1400 described below
with
reference to FIG. 14. In some examples, the determination of the interactivity
scores
includes determining the interactivity of the users.
[0083] Based on the connectedness scores and the interactivity scores, the
example
user ranker 208 of FIG. 2 determines an overall rank for the users (block
1114). Block
1114 may be implemented using example machine readable instructions 1500
described
-30-
CA 02740499 2011-05-17
below with reference to FIG. 15. The user ranker 208 then returns the
popularities of the
users of the social networking site 102 (e.g., to the monitor terminal 116 of
FIG. 1, to a
computer 108 of a user of the social networking site 102 of FIG. 1, and/or to
another
requester location) (block 1118). After returning the popularities of the
users, the
example instructions 1100 may end or iterate to continue processing
interactions and/or
responding to requests.
[0084] FIG. 12 is a flowchart representative of example machine readable
instructions
1200 which may be executed to process interactions. The example instructions
1200 may
be executed to implement the example interactivity monitor 206 of FIG. 2 to
execute
block 1104 of FIG. 11. The instructions 1200 may begin when the data
collection
monitor 214 determines that it is time to process interactions between users
on the social
networking site 102.
[0085] To process interactions, the example interactivity monitor 206
identifies
interactions between users on the social networking site 102 (block 1202). In
some
examples, the interactivity monitor 206 discards or ignores those interactions
that are
identified but were previously processed. For example, the interactivity
monitor 206 may
ignore at least a portion of a relational matrix that is updated with a new or
additional
interaction after a previous interaction processing sequence. The example
blocks 1204-
1216 iterate in a for-loop as described below. In particular, the blocks 1204-
1216 may be
iterated for each interaction identified by the interactivity monitor 206 in
block 1202.
[0086] For a selected interaction, the interactivity monitor 206 determines
whether the
action is a response interaction corresponding to a previous initial
interaction (block
1204). For example, the interactivity monitor 206 may determine that a status
update A
-31-
CA 02740499 2011-05-17
by a user is an initial interaction (e.g., is not a response interaction), but
may determine
that a comment B to the status update A is a response interaction to the
earlier status
update interaction A. If the selected interaction is not a response
interaction (e.g., the
interaction is an initial interaction) (block 1204), the example interactivity
monitor 206
generates a new relational matrix corresponding to the selected interaction
(block 1206).
In contrast, if the selected interaction is a response interaction (block
1204), the
interactivity monitor loads a previously-created relational matrix
corresponding to the
initial interaction to which the selected interaction is a response (block
1208).
[0087] After generating a new relational matrix (block 1206) or loading a
relational
matrix (block 1208), the example interactivity monitor 206 identifies a user
(e.g., the user
i 406 of FIG. 4) that performed the interaction (block 1210). For example, the
user that
performs a status update is the poster of the update and the person that
performs a
comment to a status update is the commenter. Thus, the interactivity monitor
206
identifies the poster of a status update or to a user commenting on a status
update. The
interactivity monitor 206 also identifies user(s) (e.g., the user(s) 408-412
of FIG. 4)
receiving the interaction (block 1212). For example, a user receiving the
interaction may
be a user 408 who is a direct contact of the user i 406 and receives a
notification that the
user i 406 has updated his or her status.
[0088] Based on the identified performing and receiving users, the
interactivity
monitor 206 populates the relational matrix with interaction count(s) (block
1214). The
example interactivity monitor 206 then stores the relational matrix (block
1216). After
storing the relational matrix (block 1216), the for-loop may iterate to select
another
identified interaction or may return control to the example instructions 1100
of FIG. 11.
-32-
CA 02740499 2011-05-17
While the example instructions 1200 have been described with reference to a
relational
matrix, the example instructions may additionally or alternatively be used
with a vector
or other data structure.
[0089] FIG. 13 is a flowchart representative of example machine readable
instructions
1300 which may be executed to determine connectedness scores of users on a
social
networking site (e.g., the social networking site 102 of FIG. 1). The example
instructions
1300 may be used to implement the example connectedness monitor 204 of FIG. 2
to
execute block 1110 of FIG. 11.
[0090] The example instructions 1300 may enter from block 1108 of FIG. 11.
The
example connectedness monitor 204 iterates blocks 1302-1312 for each user on
the
example social networking site 102. For a selected user (e.g., the user 302 of
FIG. 3), the
connectedness monitor 204 determines a number of direct contacts (e.g., the
users 304a-
304d) of the user 302 (block 1302). The connectedness monitor 204 further
determines a
number of indirect contacts (e.g., the users 306-308) of the user 302 (block
1304).
Additionally, the connectedness monitor 204 determines which contacts 304-308
have
restricted connections to the user 302 (block 1306).
[0091] The example connectedness monitor 204 then applies weights to the
restricted
connections (block 1308). The connectedness monitor 204 may apply weights to
different numbers of direct 304a-304d and indirect contacts 306-308 based on
the
restrictions between respective ones of the users 304-308 and the user 302.
For example,
the connectedness monitor 204 may apply a higher (e.g., larger) weight (or a
unit weight)
to the user 304b who has an unrestricted connection to the user 302, and may
apply a
lower (e.g., smaller) weight to the user 304c who has a restricted connection
to the user
-33-
CA 02740499 2011-05-17
302. The connectedness monitor 204 determines a connectedness for the selected
user
302 based on the unrestricted direct contacts 304a-304b, the unrestricted
indirect contacts
306-308, and the restricted direct and/or indirect contacts (block 1310). For
example, the
connectedness monitor 204 may determine the connectedness Ciweight of the
selected user
using Equation 4 above.
[0092] The example connectedness monitor 204 determines a connectedness
score of
the selected user 302 based on the connectedness (block 1312). For example,
the
connectedness monitor 204 may determine the connectedness score based on the
connectedness of the selected user 302 compared to the connectedness of other
users 304-
308 of the social networking site 102. The connectedness monitor 204 may then
store the
connectedness and the connectedness score for the selected user 302 (e.g., in
the database
118 of FIG. 2) (block 1314). After storing the connectedness and the
connectedness
score, the example instructions 1300 may iterate blocks 1302-1314 for
additional users or
may return control to block 1112 of FIG. 11.
[0093] FIG. 14 is a flowchart representative of example machine readable
instructions
1400 which may be executed to determine an interactivity score of a user on a
social
networking site (e.g., the social networking site 102 of FIG. 1). The example
instructions
may be used to implement the example interactivity monitor 206 of FIG. 2 to
execute
block 1112 of FIG. 11. Blocks 1402-1408 of FIG. 14 may iterate for each user
of a
number of users for which an interactivity score is to be generated.
[0094] The example interactivity monitor 206 may begin after block 1110 of
the
example instructions 1100 by identifying relational matrices having an initial
interaction
performed by the selected user (e.g., the user i 406 of FIG. 4) (block 1402).
For example,
-34-
CA 02740499 2011-05-17
the interactivity monitor 206 may identify those relational matrices
previously generated,
updated, and/or stored in the database 118 of FIG. 2 by the interactivity
monitor 206
during the processing of interactions on the social networking site 102 of
FIG. 1. The
interactivity monitor 206 sums the interaction counts from the identified
relational
matrices to identify an interactivity for the selected user i 406 (block
1404). In some
examples, the relational matrices are based on an initial interaction
performed by the user
i 406, and therefore the user i 406 either performs or receives the initial
interaction(s)
and/or any response interaction(s) included in the relational matrices, and
the interaction
counts may be attributed to the user i 406. In some other examples, however,
the
relational matrices may include interaction counts that are not associated
with the user i
406. In this case the interactivity monitor 206 determines the interaction
counts for the
user i 406 by, for example, counting interaction counts in the rows and/or
columns
corresponding to the user i 406.
[0095] The example interactivity monitor 206 then determines the
interactivity score
based on the interactivity (block 1406). For example, the interactivity
monitor 206 may
determine the interactivity score as a percentile rank of interaction counts
for the user i
406 compared to the number of interaction counts for other users (e.g., the
users 408-412)
and/or as a number of interaction counts. The interactivity monitor 206 stores
the
interactivity and the interactivity score for the selected user i 406 (block
1408). The
example blocks 1402-1408 may then iterate to determine an interactivity score
for
another user or may return control to block 1114 of FIG. 11.
[0096] FIG. 15 is a flowchart representative of example machine readable
instructions
1500 which may be executed to determine an overall (e.g., composite) rank of a
user on a
-35-
CA 02740499 2011-05-17
social networking site (e.g., the example social networking site 102 of FIG.
1). The
example instructions 1500 may be used to implement the example user ranker 208
to
execute block 1114 of FIG. 11. The example blocks 1502-1506 may be iterated
for each
user of a number of users to be ranked.
[0097] The example user ranker 208 loads a connectedness score and an
interactivity
score (block 1502). For example, the user ranker 208 receives the
connectedness score
from the connectedness monitor 204 (e.g., generated by executing blocks 1302-
1310 of
FIG. 13) and receives the interactivity score from the interactivity monitor
206 (e.g.,
generated by executing blocks 1402-1406 of FIG. 14). The user ranker 208 then
applies
weights to connectedness and interactivity scores based on the query (block
1504). For
example, the user ranker 208 may apply equal weights to the connectedness and
interactivity scores or may apply a higher weight to one of the connectedness
score or the
interactivity score and a lower weight to the other of the scores. For
example, the
connectedness score may have a higher weight than the interactivity score if
the user
request query 210 indicates that the connectedness score is more important to
the
requester than the interactivity score.
[0098] The example user ranker 208 then determines the user rank based on
the
connectedness and interactivity scores (block 1506). After determining the
user rank, the
user ranker 208 may iterate blocks 1502-1506 for additional users or may
return control
to block 1116 of FIG. 11.
[0099] FIG. 16 is a flowchart representative of example machine readable
instructions
1600 which may be executed to determine a network efficacy score (e.g., for
the social
networking site 102 of FIG. 1). The example instructions 1600 may be executed
by one
-36-
CA 02740499 2011-05-17
or more of the example user selector 202, the example connectedness monitor
204, the
example interactivity monitor 206, and/or the example network efficacy
determiner 218
to generate the network efficacy score(s) 220 (FIG. 2) for the social
networking site 102.
[01001 The example connectedness monitor 204 may begin by determining
connectedness scores for users of the social networking site 102 (block 1602).
Block
1602 may be implemented by the example connectedness monitor 204 of FIG. 2 by
executing the example machine readable instructions 1300 of FIG. 13. The
example
connectedness monitor 204 and/or the network efficacy determiner 218 may
determine an
average user connectedness score for the users of the social networking site
102 (block
1604).
[0101] The example interactivity monitor 206 then determines interactivity
scores for
the users of the social networking site 102 (block 1606). Block 1606 may be
implemented by the interactivity monitor 206 by executing the example machine
readable
instructions 1400 of FIG. 14. The example interactivity monitor 206 and/or the
network
efficacy determiner 218 may determine an average user interactivity score for
the users of
the social networking site 102 (block 1608).
[0102] The example connectedness monitor 204 further determines network
constancy
scores for the users of the social networking site 102 (block 1610). Block
1610 may be
implemented by the example connectedness monitor 204 of FIG. 2 by executing
the
example machine readable instructions 1700 described with reference to FIG. 17
below.
The example connectedness monitor 204 and/or the network efficacy determiner
218 may
determine an average user network constancy score for the users of the social
networking
site 102 (block 1612). While the example blocks 1604, 1608, and 1612 determine
the
-37-
CA 02740499 2011-05-17
average connectedness, the average interactivity, and the average network
constancy
scores for the users, respectively, the example blocks 1604, 1608, and 1612
may
additionally or alternatively determine a median score, a mode score, and/or
any other
score that is representative of the user scores on the social networking site
102.
[0103] The example network efficacy determiner 218 then determines a
network
efficacy score 220 based on the average connectedness score, the average
interactivity
score, and/or the average network constancy score (block 1614). For example,
the
network efficacy determiner 218 may subtract the network constancy score
(where a
higher network constancy score represents a higher network instability) from
the sum of
the interactivity score and the connectedness score. However, other
formulations of the
network efficacy determiner 218 may be used to determine a network efficacy
score.
After determining the network efficacy score 220, the example network efficacy
determiner 218 stores the network efficacy score 220 for later retrieval
and/or transmittal.
In some examples, the network efficacy determiner 218 may transmit the network
efficacy score 220 to a requester of the network efficacy score. The example
instructions
1600 may then end.
[0104] FIG. 17 is a flowchart representative of example machine readable
instructions
1700 which may be executed to determine a network constancy score (e.g., the
network
constancy score 220 of FIG. 2) of a social networking site (e.g., the social
networking site
102 of FIG. 1). The example instructions 1700 may be executed by the
connectedness
monitor 204 of FIG. 2 to implement block 1610 of FIG. 16. Blocks 1702-1712 of
the
example instructions 1700 may be iterated for multiple users of the social
networking site
102.
-38-
CA 02740499 2011-05-17
[0105] The example connectedness monitor 204 may begin an iteration of a
loop by
selecting a user of the example social networking site 102 (e.g., the user 302
of FIG. 3).
For the selected user 302, the connectedness monitor 204 identifies the
contacts (e.g., the
users 304-308) who are connected to the selected user 302 within a number N of
degrees
of connection (e.g., up to a third-degree connection) (block 1702). The
connectedness
monitor 204 then determines the connections between the identified contacts
(block
1704). For example, the connectedness monitor 204 may determine that there is
a
second-degree connection between the user 304a and each of the users 304b-
304d, etc.
[0106] The connectedness monitor 204 simulates a removal of the user 302
from the
social networking site 102 (block 1706). For example, the connectedness
monitor 204
may view the user 304a as disconnected from the users 304b-304d. Based on the
simulated removal, the connectedness monitor 204 determines a number of broken
connections that result (block 1708). The network constancy score for the user
302 may
be determined based on the connections between the identified users 304-308
and the
broken connections resulting from the removal of the user 302 (block 1710).
For
example, the connectedness monitor 204 may determine the network constancy
score as
the ratio of broken connections to the number of connections between the
identified users
(e.g., when the user 302 is still considered as in the social networking site
102).
However, other formulations of the network constancy score may be determined.
[0107] The example connectedness monitor 204 then stores the network
constancy
score for the user 302 (e.g., in the database 118 of FIG. 2) (block 1712).
After storing the
network constancy score, the connectedness monitor 204 may iterate by
selecting another
-39-
CA 02740499 2011-05-17
user of the social networking site 102 and looping control to block 1702 or
the example
instructions 1700 may end and return control to block 1612 of FIG. 16.
[0108] FIG. 18 is a diagram of an example processor system 1800 that may be
used to
execute the example machine readable instructions 1100, 1200, 1300, 1400,
1500, 1600,
and 1700 described in FIGS. 11-17, as well as to implement the social network
monitor
112 described in FIG. 2. The example processor system 1800 includes a
processor 1802
having associated memories, such as a random access memory (RAM) 1804, a read
only
memory (ROM) 1806 and a flash memory 1808. The processor 1802 is coupled to an
interface, such as a bus 1812 to which other components may be interfaced. In
the
illustrated example, the components interfaced to the bus 1812 include an
input device
1814, a display device 1816, a mass storage device 1818, a removable storage
device
drive 1820, and a network adapter 1822. The removable storage device drive
1820 may
include associated removable storage media 1824 such as magnetic or optical
media. The
network adapter 1822 may connect the processor system 1800 to an external
network
1826.
[0109] The example processor system 1800 may be, for example, a
conventional
desktop personal computer, a notebook computer, a workstation or any other
computing
device. The processor 1802 may be any type of processing unit, such as a
microprocessor
from the Intel Pentium family of microprocessors, the Intel Itanium family
of
microprocessors, and/or the Intel XScale family of processors. The memories
1804,
1806 and 1808 that are coupled to the processor 1802 may be any suitable
memory
devices and may be sized to fit the storage demands of the system 1800. In
particular, the
-40-
CA 02740499 2011-05-17
flash memory 1808 may be a non-volatile memory that is accessed and erased on
a block-
by-block basis.
101101 The input device 1814 may be implemented using a keyboard, a mouse,
a
touch screen, a track pad, a barcode scanner or any other device that enables
a user to
provide information to the processor 1802.
101111 The display device 1816 may be, for example, a liquid crystal
display (LCD)
monitor, a cathode ray tube (CRT) monitor or any other suitable device that
acts as an
interface between the processor 1802 and a user. The display device 1816 as
pictured in
FIG. 18 includes any additional hardware required to interface a display
screen to the
processor 1802.
[0112] The mass storage device 1818 may be, for example, a conventional
hard drive
or any other magnetic, optical, or solid state media that is readable by the
processor 1802.
[0113] The removable storage device drive 1820 may, for example, be an
optical
drive, such as a compact disk-recordable (CD-R) drive, a compact disk-
rewritable (CD-
RW) drive, a digital versatile disk (DVD) drive or any other optical drive. It
may
alternatively be, for example, a magnetic media drive and/or a solid state
universal serial
bus (USB) storage drive. The removable storage media 1824 is complimentary to
the
removable storage device drive 1820, inasmuch as the media 1824 is selected to
operate
with the drive 1820. For example, if the removable storage device drive 1820
is an
optical drive, the removable storage media 1824 may be a CD-R disk, a CD-RW
disk, a
DVD disk or any other suitable optical disk. On the other hand, if the
removable storage
device drive 1820 is a magnetic media device, the removable storage media 1824
may be,
for example, a diskette or any other suitable magnetic storage media.
-41-
CA 02740499 2014-03-11
[0114] The network adapter 1822 may be, for example, an Ethernet adapter, a
wireless local
area network (LAN) adapter, a telephony modem, or any other device that allows
the processor
system 1800 to communicate with other processor systems over a network. The
external
network 1826 may be a LAN, a wide area network (WAN), a wireless network, or
any type of
network capable of communicating with the processor system 1800. Example
networks may
include the Internet, an intranet, and/or an ad hoc network.
[0115] While the above specification described example systems, methods and
articles of
manufacture, the examples are not the only way to implement such systems,
methods and articles
of manufacture. Therefore, although certain example methods, apparatus and
articles of
manufacture have been described herein, the scope of coverage of this patent
is not limited
thereto. On the contrary, this patent covers all methods, apparatus and
articles of manufacture
fairly falling within the scope of the appended claims either literally or
under the doctrine of
equivalents.
- 42 -
