JP6157395B2 - Link complement device, link complement method, and link interpolation program - Google Patents

Description

  The present invention relates to an apparatus, a method, and a program for complementing a link in a contact network.

Conventionally, among websites published on the Internet, there are personal websites managed by one or more online individuals linked to offline individuals.
Here, the offline individual means each real user who uses the network (Internet) and has one or more personalities on the network. Personalities on the network are referred to herein as online individuals, and offline individuals and online individuals have a one-to-one or one-to-many relationship. An offline individual creates an account for each of one or more service providers via an online individual and manages one or more personal websites.
In recent years, especially among junior high school students and high school students, each person has multiple online individuals, and each online individual creates multiple personal websites, not only between their own sites, but also between sites with others. In many cases, hyperlinks are provided and information and messages are disclosed and exchanged.

Based on hyperlinks between these personal websites, an undirected graph (contact network) of friend relationships with online individuals who are administrators as nodes is generated. Often appears as an upper clique.
Therefore, by detecting this clique, it is possible to infer a fellow group formed in the real world.

However, if a part of the collected hyperlinks between personal websites is missing due to omission of observation of hyperlinks or password concealment, a clique that should actually be missed.
Non-Patent Document 1 discloses a method of predicting the presence or absence of a link by machine learning for each link distance (number of hops) between nodes.

R. N. Richtenwalter, J.M. T. T. Lussier and N.L. V. Chawla, “New Perspectives and Methods in Link Prediction,” KDD2010, pp. 243-252, 2010.

  However, since the method of Non-Patent Document 1 assumes a scale-free network, the accuracy of link prediction is not sufficient in a special network of a personal website that strongly reflects human relationships in the real world.

  An object of the present invention is to provide a link complementing device, a link complementing method, and a link complementing program capable of accurately complementing a missing link in an administrator contact network generated based on a hyperlink between personal websites. To do.

  The link complementation apparatus according to the present invention includes a storage unit that stores IDs of managers of a plurality of personal websites and link information indicating adjacency relationships by hyperlinks among the plurality of personal websites, and the link information. Based on the number of common adjacent nodes, a generation unit that generates an undirected graph with the administrator as a node and a pair of nodes that do not have a direct link in the graph generated by the generation unit A classification unit that classifies a plurality of types, and for each of the types, generation of teacher data for machine learning and predetermined machine learning based on a feature amount of a pair of nodes predicts and complements a link loss A section.

  The classification unit may classify a pair of nodes having no direct link into a plurality of types based on the number of hops between the nodes and the number of common adjacent nodes.

  The generation unit may generate the undirected graph by excluding link information in which the link source personal website is not a predetermined type.

  The generation unit may determine the presence or absence of a link between the nodes in the undirected graph based on the direction or number of hyperlinks between the nodes.

  The storage unit may further store personal attribute information, and the generation unit may extract the manager and the link information based on a specified condition of the personal attribute information.

  The link complementing method according to the present invention refers to a storage unit that stores IDs of administrators of a plurality of personal websites and link information indicating adjacency relationships by hyperlinks between the plurality of personal websites, and Based on the information, a generation step of generating an undirected graph with the administrator as a node, and a pair of nodes having no direct link in the graph generated in the generation step is set to the number of common adjacent nodes. Based on the classification step for classifying into a plurality of types, and for each type, generation of teacher data for machine learning and predetermined machine learning based on the feature amount of a node pair predicts and compensates for link loss The computer executes the complementary step.

  The link complementing program according to the present invention refers to a storage unit that stores IDs of managers of a plurality of personal websites and link information indicating adjacency relationships by hyperlinks between the plurality of personal websites. Based on the information, a generation step of generating an undirected graph with the administrator as a node, and a pair of nodes having no direct link in the graph generated in the generation step is set to the number of common adjacent nodes. Based on the classification step for classifying into a plurality of types, and for each type, generation of teacher data for machine learning and predetermined machine learning based on the feature amount of a node pair predicts and compensates for link loss And causing the computer to execute a complementary step.

  ADVANTAGE OF THE INVENTION According to this invention, in the administrator's contact network produced | generated based on the hyperlink between personal websites, the missing link can be complemented with sufficient accuracy.

It is a figure which shows the relationship between the personal website which concerns on embodiment, and its administrator. It is a figure which shows the relationship between the service provider which concerns on embodiment, an account, and a personal website. It is a schematic diagram which shows the result by which online ID which concerns on embodiment was allocated. It is a block diagram which shows the function structure of the link complementation apparatus which concerns on embodiment. It is a figure which shows the collection log | history management table which concerns on embodiment. It is a figure which shows the relationship table between sites which concerns on embodiment. It is a figure which shows the personal attribute table which concerns on embodiment. It is a figure which shows the example of classification | category of the node pair which concerns on embodiment. It is a flowchart which shows the graph production | generation process which concerns on embodiment. It is a flowchart which shows the link complementation process which concerns on embodiment.

Hereinafter, an example of an embodiment of the present invention will be described.
The link complementing apparatus 1 according to the present embodiment is an apparatus that generates a contact network having online individuals as nodes and interpolates missing links based on hyperlinks between personal websites managed by online individuals. is there. The link complementing apparatus 1 may be various information processing apparatuses (computers) such as a server apparatus and a PC (Personal Computer).

FIG. 1 is a diagram showing a relationship between a personal website according to the present embodiment and an administrator thereof.
An offline individual who is a real person manages one or a plurality of online individuals on a network (Internet). Online individuals also create accounts for each of one or more service providers and manage one or more personal websites. Hereinafter, the term “administrator” refers to an online individual.

  Each online individual, for example, is a student at the same school, is part of a group with the same hobby, or has a certain relationship with others online. Therefore, hyperlinks are often referenced between personal websites managed by a plurality of online individuals.

Here, the personal website refers to a website for an online individual or a plurality of individuals to publish information about themselves or exchange messages with others online. A personal website is a collection of HTML files provided by a service provider for each function or service for each online individual who creates an account.
For example, the following types of personal websites are each provided by a plurality of service providers.

Prof (profile) ... A website where you can publish your personal profile Gesbu (guest book) ... A website where visitors can post comments as a history Real (real time) ... You can post your current situation in short sentences Website Blog: A website where you can publish daily records My link ... A website where you can publish links to other people's personal websites Homepage (Homepage) ... A personal website that can be used for multiple purposes

  Since online individuals create the above-mentioned multiple types of personal websites with different accounts for each service provider, they are often not linked (identified) with the same ID. For example, an online individual who has “Online ID (OnID) = 1” manages Prof, Gesbu, and Real. These personal websites do not have the information “OnID = 1” and are managed with different account IDs (AcID = 1 and 2).

  FIG. 2 is a diagram showing the relationship between the service provider, the account, and the personal website according to the present embodiment.

An online individual (OnID = 1) registers, for example, an account 1 with a service provider SP-A that provides a prof and a gebus, and manages the prof and the gebs. Further, the same online individual (OnID = 1) registers the account 2 with the service provider SP-B providing the real and guest, and manages the real.
In this way, an online individual can select a favorite personal website from a plurality of service providers and manage a plurality of personal websites by a plurality of accounts.

  The link complementing apparatus 1 collects personal websites within a predetermined range, and then, based on the link information between the personal websites, the same online for the personal websites that are the same online individuals who are administrators. An ID (OnID) is assigned, and a plurality of personal websites are classified for each online individual.

  FIG. 3 is a schematic diagram showing a result of the online ID assigned by the link complementing apparatus 1 according to the present embodiment.

One or more personal websites assigned the same online ID (OnID) are not necessarily the same in account ID (AcID), and are different if personal websites provided by different service providers are selected Identified by account ID.
Here, the link structure between the online individuals who are managers is grasped by visualizing the hyperlink that exists between the personal websites grouped by the online ID. As a result, for example, regarding a trouble caused by a human relationship such as network bullying, the human relationship on the network can be provided to a teacher or the like as information necessary for student guidance.

FIG. 4 is a block diagram illustrating a functional configuration of the link complementation apparatus 1 according to the present embodiment.
The link complementation apparatus 1 includes a control unit 10, a storage unit 20, a communication unit 30, an input unit 40, and an output unit 50.

  The control unit 10 is a part that controls the entire link complementing device 1, and appropriately reads and executes various programs stored in the storage unit 20, thereby cooperating with the hardware described above and various types in the present embodiment. The function is realized. The control unit 10 may be a CPU (Central Processing Unit). In addition, the function of each part with which the control part 10 is provided is mentioned later.

  The storage unit 20 is a storage area for various programs and various data for causing the hardware group to function as the link complementation apparatus 1, and may be a hard disk (HDD). Specifically, the storage unit 20 stores a program (link supplement program) that is executed by the control unit 10 in order to realize various functions of the present embodiment.

  Furthermore, the storage unit 20 includes a site storage DB 21 and a site management DB 22. The site storage DB 21 stores page data (HTML file group) of a personal website acquired by the program. Further, the site management DB 22 stores a collection history management table 221, an inter-site relation table 222, and a personal attribute table 223 described later that are created or edited by a program.

  In the collection history management table 221, the history of the personal website collected from the Internet according to a predetermined rule is recorded. Information on hyperlinks between personal websites is recorded in the inter-site relation table 222. The personal attribute table 223 is recorded when attribute information in the real world regarding an online individual is provided.

Further, when an online ID for identifying an online individual who is an administrator of each personal website is assigned based on the information in the inter-site relation table 222, the collection history management table 221 and the inter-site relation table 222 are updated. .
Note that existing proposal methods can be used for collecting personal websites and assigning online IDs (for example, Japanese Patent Application No. 2011-071109, Japanese Patent Application No. 2010-108242).

  FIG. 5 is a diagram showing the collection history management table 221 stored in the site management DB 22 according to the present embodiment.

  The collection history management table 221 stores a collection ID, a root URL, a link source URL, a representative URL (URL (U)) of a personal website, a storage destination, the number of hops, an online ID (OnID (U)), a collection date and time, and the like. To do.

  Here, the collection ID is an identification number given each time the collection process is executed. The root URL is the URL of the personal website that is the starting point for collection designated when performing the collection process. The storage destination is a URL indicating the storage location of the target personal website in the site storage DB 21.

  The number of hops is the number of hops from the root node when a designated personal website is a root node and a hyperlink between adjacent linked personal websites is one hop.

FIG. 6 is a diagram showing the inter-site relation table 222 stored in the site management DB 22 according to the present embodiment.
The inter-site relation table 222 includes a collection ID, link source personal website information (URL (U), Type (U), C (U), AcID (U), OnID (U)), link destination personal web. Site information (URL (V), Type (V), C (V), AcID (V), OnID (V)), number of links (N (U → V)) and link occurrence date (Ldate (U → V) )) Etc.
Note that C (U) and C (V) are classifications (classes) representing the usage forms of the site, and are determined from the URL of the personal website. Specifically, Class A is a personal website created by Prof and Hompe to classify and distinguish online individuals from others. Class B is a personal web site created by an online individual attached to Class A, with classifying Gesbu and My Links. Class C is a personal web site created by real and blogs that are categorized and used to distinguish online individuals from others or in association with Class A.

  Here, AcID includes an identifier of a service provider and an identifier of an account issued for each service provider. These identifiers are identified by the URL of the personal website. Here, if the account is the same for the same service provider, the administrator (online individual) can be considered the same, but if the service provider is different, the administrator is the same even if the account is the same. Is not limited.

  FIG. 7 is a diagram showing the personal attribute table 223 stored in the site management DB 22 according to the present embodiment.

The personal attribute table 223 stores an online ID (OnID), a representative URL of a personal website, a real name, a handle name, a gender, a region, a school, a grade, a class, and the like.
Such attribute information is provided from an organization such as a school or extracted from text information in a personal website, and is used to select nodes and links for generating a graph.

  The communication unit 30 is a network adapter used when the link complementing apparatus 1 transmits and receives information to and from other apparatuses, and accesses the server 100 that manages the personal website via the network (Internet). The page data is acquired and provided to the control unit 10.

  The input unit 40 is an interface device that accepts an instruction input from a user to the link complementing device 1. The input unit 40 is configured by, for example, a keyboard, a mouse, a touch panel, and the like.

  The output unit 50 includes a display device that displays a screen for accepting data input to the user and displays a screen of a processing result by the link complementation device 1. Further, the output unit 50 may include various output devices such as a printer in addition to a display device such as a cathode ray tube display device (CRT) or a liquid crystal display device (LCD).

Next, the function of the control unit 10 will be described in detail.
The control unit 10 includes a graph generation unit 11 (generation unit), a type classification unit 12 (classification unit), a link complementation unit 13 (complementation unit), and an application unit 14. Each of these units is a functional block realized by executing a link complement program.

The graph generation unit 11 generates an undirected graph having an administrator (online individual) as a node based on the link information in the inter-site relation table 222.
At this time, the graph generation unit 11 generates a graph by excluding link information in which the link source personal website is not a predetermined type. The predetermined type is, for example, “prof”, “hompe”, and “my link” that include static links representing human relationships and are classified into static sites.

  Further, the graph generation unit 11 determines the presence or absence of a link between nodes in the undirected graph based on the direction or number of hyperlinks between nodes. For example, when there are one or more hyperlinks in both directions, or when there are five or more hyperlinks in one direction, a predetermined rule may be set.

In addition, the graph generation unit 11 extracts the manager and link information based on the designated personal attribute information condition. Specifically, the graph generation unit 11 extracts, for example, an administrator list composed of students of a specific school from the personal attribute table 223, and links information whose link source or link destination is included in the administrator list to the inter-site relation. A graph is generated by extracting from the table 222.
In addition, both the link source and the link destination extract link information included in the administrator list, extract link information from a specific administrator to a predetermined number of hops, and various other extraction conditions. Is possible.

  The type classification unit 12 includes a plurality of pairs of nodes that do not have a direct link in the graph generated by the graph generation unit 11 based on the number of hops between the nodes and the number of common adjacent nodes (Common Neighbors). It is classified into the type.

FIG. 8 is a diagram illustrating an example of node pair classification according to the present embodiment.
In this example, an administrator list including administrators 1 to 7 is given, and an undirected graph having these administrators as nodes is generated by the graph generation unit 11.

From this graph, 21 node pairs can be obtained, and 7 of them have been found that have a direct link, that is, one hop number.
The type classifying unit 12 classifies a pair of nodes having no direct link, that is, having a hop count of 2 or more into a plurality of types. In this example, the number of hops is 3 or more, the number of hops is 2 and the number of common adjacent nodes is 1, and the number of hops is 2 and the number of common adjacent nodes is 2 or more. The case of classification is shown.

For each type classified by the type classification unit 12, the link complementation unit 13 predicts link deficiencies by generating teacher data for machine learning and predetermined machine learning based on feature quantities of node pairs. To do.
An existing machine learning algorithm can be used. For example, a decision tree, a Random Forest, a support vector machine, or the like is used.
In addition, as for the feature amount of a pair of nodes, for example, conventionally proposed ones such as Common Neighbors, Adamic / Adar, Jaccard's Coefficient, Preferred Attachment, Katzβ, PropFlow, and the like can be used. May be.

  Note that the types of feature values used for machine learning may be different for each classified type. For example, Admic / Adar is preferentially used when the number of common adjacent nodes is less than 6, and Preferential Attachment is preferentially used when the number is 6 or more.

  The application unit 14 is a functional block that provides information of the site management DB 22 to the user. For example, the application unit 14 performs processing such as visualizing hyperlinks between managers of personal websites based on the link information, and outputs the processing result to the output unit 50 to provide to the user.

FIG. 9 is a flowchart showing the graph generation processing according to the present embodiment.
In step S <b> 1, the graph generation unit 11 acquires from the personal attribute table 223 a list of managers whose personal attributes match a condition (for example, a student at a specific school).
Information different from personal attribute information such as the number of hops from the route when collecting personal websites may be used as a condition. Further, the graph generation unit 11 may extract all managers without designating conditions.

In step S <b> 2, the graph generation unit 11 acquires link information included in the administrator list in step S <b> 1 by the link source or link destination administrator from the inter-site relation table 222.
Note that the graph generation unit 11 may acquire link information included in the administrator list by both the link source administrator and the link destination administrator, and the acquisition condition may be set as appropriate.

  In step S3, the graph generation unit 11 includes the link information acquired from the inter-site relation table 222 in step S2 and the link source personal website is a static type (for example, prof, hompe, my link). Select information. For example, the graph generation unit 11 may select only link information in which the type of the personal website of the link source is My Link.

  In step S4, the graph generation unit 11 generates an undirected weight between nodes satisfying a predetermined condition (for example, one or more hyperlinks exist mutually) based on the link information selected in step S3. Generate an undirected graph with links.

FIG. 10 is a flowchart showing the link complement processing according to the present embodiment.
In step S <b> 11, the type classification unit 12 acquires a node pair in which all the managers of nodes in the graph are included in the manager list.

In step S12, the type classification unit 12 calculates the number of hops between nodes and the number of common adjacent nodes from the generated graph information for the node pair acquired in step S11.
Note that the calculation of the number of common adjacent nodes may exclude an administrator node not included in the administrator list.

  In step S <b> 13, the type classification unit 12 classifies a node pair having two or more hops, that is, no direct link, into a plurality of types according to the number of hops and the number of common adjacent nodes.

  In step S14, the link complementation part 13 estimates the presence or absence of a link by predetermined | prescribed machine learning for every type classified by step S13.

  In step S15, the link complementation unit 13 registers the information of the node pair estimated to have a link in step S14 in the inter-site relation table 222 or another table. When the inter-site relation table 222 is used, since the estimated link is undirected, the link complementation unit 13 adds two records as link information to both nodes, for example.

According to the present embodiment, the link complementing apparatus 1 classifies node pairs into a plurality of types based on the number of common adjacent nodes in a contact network of an administrator generated based on hyperlinks between personal websites. Predict the presence or absence of a node every time. Therefore, the link complementation apparatus 1 can complement a missing link with high accuracy in a special network of a personal website that strongly reflects real-world human relationships.
Furthermore, the link complementation apparatus 1 classifies the node pairs based on the number of hops between the nodes. Thereby, the link complementation apparatus 1 can complement a missing link with high accuracy.

  The link complementing apparatus 1 excludes link information that is not a static type of the link source personal website from the collected link information. Therefore, the link complementation apparatus 1 can generate a contact network that more reflects the real world.

  The link complementation apparatus 1 determines the presence or absence of undirected weightless links in the contact network according to the conditions and / or number of hyperlinks between nodes, or both conditions. Therefore, the link complementation apparatus 1 can generate a contact network efficiently based on the directed hyperlink.

  The link complementation apparatus 1 stores personal attribute information, and extracts an administrator and link information based on specified personal attribute information conditions. Therefore, the link complementation apparatus 1 can efficiently generate a contact network in a specified specific range, and can efficiently detect a clique.

  As mentioned above, although embodiment of this invention was described, this invention is not restricted to embodiment mentioned above. Further, the effects described in the present embodiment are merely a list of the most preferable effects resulting from the present invention, and the effects of the present invention are not limited to those described in the present embodiment.

  The link complementing method by the link complementing apparatus 1 is realized by software. When realized by software, a program constituting the software is installed in the information processing apparatus (link complementing apparatus 1). These programs may be recorded on a removable medium such as a CD-ROM and distributed to the user, or may be distributed by being downloaded to the user's computer via a network.

1 Link Complementary Device 10 Control Unit 11 Graph Generation Unit (Generation Unit)
12 Type classification part (classification part)
13 Link completion part (complement part)
14 Application section 20 Storage section 21 Site storage DB
22 Site management DB
30 Communication unit 40 Input unit 50 Output unit 221 Collection history management table 222 Inter-site relation table 223 Personal attribute table

Claims (7)

A storage unit that stores IDs of managers of a plurality of personal websites and link information indicating adjacency relationships by hyperlinks between the plurality of personal websites;
Based on the link information, a generation unit that generates an undirected graph with the administrator as a node;
In the graph generated by the generating unit, a classifying unit that classifies a pair of nodes having no direct link into a plurality of types based on the number of common adjacent nodes;
A link complementing device, comprising: a complementing unit that predicts and supplements a link loss by generating teacher data for machine learning and predetermined machine learning based on a feature amount of a node pair for each type.   The link complementation device according to claim 1, wherein the classification unit classifies the pair of nodes having no direct link into a plurality of types based on the number of hops between the nodes and the number of common adjacent nodes.   The link complementation device according to claim 1 or 2, wherein the generation unit generates the undirected graph by excluding link information whose link source personal website is not a predetermined type.   The link complementation device according to any one of claims 1 to 3, wherein the generation unit determines the presence or absence of a link between the nodes in the undirected graph based on the direction or number of hyperlinks between the nodes. The storage unit further stores personal attribute information,
The link complementation device according to any one of claims 1 to 4, wherein the generation unit extracts the manager and the link information based on a specified condition of the personal attribute information. Reference is made to a storage unit that stores IDs of managers of a plurality of personal websites and link information indicating adjacency relationships by hyperlinks between the plurality of personal websites, and the manager is identified based on the link information. A generation step for generating an undirected graph as a node;
A classifying step of classifying a pair of nodes having no direct link into a plurality of types based on the number of common adjacent nodes in the graph generated in the generating step;
A link complementing method in which a computer executes a complementing step of predicting and complementing a link loss by generation of teacher data for machine learning and predetermined machine learning based on a feature amount of a node pair for each type. . Reference is made to a storage unit that stores IDs of managers of a plurality of personal websites and link information indicating adjacency relationships by hyperlinks between the plurality of personal websites, and the manager is identified based on the link information. A generation step for generating an undirected graph as a node;
A classifying step of classifying a pair of nodes having no direct link into a plurality of types based on the number of common adjacent nodes in the graph generated in the generating step;
A link for causing the computer to execute a complementing step of predicting and complementing a link loss by generating teacher data for machine learning and predetermined machine learning based on a feature amount of a node pair for each type. Complementary program.

Images