Paper Abstract and Keywords |
Presentation |
2005-11-10 14:35
Relationship calculation on weighted directed graph and its validity examination in ranking system
-- Application on Semantic Web -- Shigeki Hino (NTT) |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
Graph algorithms are increasingly used in the back-end of internet services. However most of them are optimized for some specific graph structures such as the hierarchical structure. Here we examine the application of general graph algorithm which does not depend on any specific structure. As an example the author focus on the problem of node relationship calculation by propagation of weight in a graph whose branch weight represents the strength of relation between nodes. General graph algorithm usually suffers from combinatorial explosion of the path generation. The author propose a method to simplify the calculation while still preserve the ranking of the results. If a reference point is set to a directed tree chosen from priority branches near the starting node, a subgraph consists only of forward branches can be generated. The proposed method limits the target paths to the paths on the subgraph. When the starting node has few neighbors, we can achieve results almost equal to the calculation method using all the paths. Reasonable results can be achieved when applied to the network of human relations or dependency relations of companies. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
directed graph / branch weight / propagation of weight / internet / human relations / dependency relations of companies / simplify the calculation / reasonable results |
Reference Info. |
IEICE Tech. Rep., vol. 105, no. 387, CAS2005-55, pp. 35-40, Nov. 2005. |
Paper # |
CAS2005-55 |
Date of Issue |
2005-11-03 (CAS, CST) |
ISSN |
Print edition: ISSN 0913-5685 |
Download PDF |
|
Conference Information |
Committee |
MSS CAS |
Conference Date |
2005-11-10 - 2005-11-11 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Yamaguchi University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
Graph theory, Petri net, Neural network, etc. |
Paper Information |
Registration To |
CAS |
Conference Code |
2005-11-CST-CAS |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Relationship calculation on weighted directed graph and its validity examination in ranking system |
Sub Title (in English) |
Application on Semantic Web |
Keyword(1) |
directed graph |
Keyword(2) |
branch weight |
Keyword(3) |
propagation of weight |
Keyword(4) |
internet |
Keyword(5) |
human relations |
Keyword(6) |
dependency relations of companies |
Keyword(7) |
simplify the calculation |
Keyword(8) |
reasonable results |
1st Author's Name |
Shigeki Hino |
1st Author's Affiliation |
Nippon Telephone and Telegraph (NTT) |
2nd Author's Name |
|
2nd Author's Affiliation |
() |
3rd Author's Name |
|
3rd Author's Affiliation |
() |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2005-11-10 14:35:00 |
Presentation Time |
25 minutes |
Registration for |
CAS |
Paper # |
CAS2005-55, CST2005-24 |
Volume (vol) |
vol.105 |
Number (no) |
no.387(CAS), no.389(CST) |
Page |
pp.35-40 |
#Pages |
6 |
Date of Issue |
2005-11-03 (CAS, CST) |