图分析

图分析算法

Pathfinding and Search: Djikstra’s algorithm
Matching and coloring: k-coloring, graph equivalence
Centrality: Degree centrality, page-rank, betweenness centrality, closeness centrality
Clustering and Community Detection: Connected components, clustering coefficient

Matching: a set of edges that do not have a set of common vertices.

Coloring: Assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints.

Centrality

Eccentricity: Maximum of minimum distances of a node to other nodes in the graph （某个点的偏心率也就是说连接该点到图中其他点的最大距离）
Central point: node with lowest eccentricity
Radius: distance: central point’s eccentricity (lowest max-distance)
Diameter: largest eccentricity (highest max-distance)

Degree Centrality: Nodes with maximum in-degree or out-degree
Betweenness Centrality: Number of all-pairs shortest paths a node participates
in
Closeness (Harmonic) Centrality: Inverse average of distance (or average inverse distance) to all other nodes

Clustering

Connected components: Set of nodes where each node is reachable from all other nodes
Clustering Coefficient

问答系统

子任务:
• Entity Linking
• Relation Linking
• Query Structure Discovery
• Identifying Logical Operators

挑战

• Lexical Gap between ontology and language:

  • String normalization – different forms of the same word
  • Query expansion – adding additional terms
  • Pattern libraries – translating complex phrasal structure into properties
  • Entailment – using previous answers + reasoning to fill in missing facts

• Ambiguity of questions and concepts

  • Context-based or corpus-based filtering
  • Constraints between concepts in the question
  • Coherence models across ontologies and concept hierarchies

• Multilingualism

• Complexity of queries

  • Multiple levels of indirection
  • Aggregation, logical comparisons, quantifiers
  • Indirect references to prior answers, nested queries
  • Constraints on the answers

• Distributed Knowledge across several KGs

  • Identifying the right KG with the answer
  • Understanding entity links between KGs
  • Predicting missing links

• Procedural, Spatial, & Temporal QA

  • Answering tasks may require different types of knowledge
  • Answer may not be an entity (e.g., “How do you make a sandwich?”
  • Event-based questions require knowledge of “before” “after” “causes”
  • Questions may use geo-coodinates, spatial relationships, containment

• Template(-free) questions

  • Question may not match existing structural patterns
  • Question might require multiple structural schemas
  • May require aggregation of answers from different query types and knowledge sources

解决方案